Grid Based Pathfinding Question

Question

•  Hey,

Im just looking at path finding and the various ways to implement it, most of the examples tend to use a grid based system that maps out the area and each point incurs a cost. Now this is all pretty logical and easy to understand, however im a bit stumpped on how i should go about generating my path finding nodes in 2d...

Its easy enough in most examples to just make a grid 100x100 and give each thing a byte value specifying how hard it is to cross, however my areas are of variable size and is not a grid as such. The collisions are not done per grid tile, they are basically a list of shapes that can cover anything from 1 pixel within a tile to all of the pixels in a tile...

I have Area.Width and Area.Height properties to work with, so i can find out how large the area is, and i have a list of the collision shapes that i can look up, however im not quite sure how to create the grid to do all the lookups on. If i did it pixel by pixel then it would take forever, however if i was to break it up into tiles some tiles may be passable but as they would contain a small part of a collision shape i would have to report it as impassible, which would lead to inaccurate results...

This isnt the best forum to put this question in, but until i get home i cant really access any of the more relevent ones...

Any help or advice would be great, and im sure im being pretty vauge or confusing so fire any questions you want over!

Wednesday, August 19, 2009 6:00 AM

• If you make pixel perfect path then it will not lead to anywhere other than performance bottleneck. I don't know about the quadtree but I did used Grids in my previous 2 games and they did quite well, although my requirement is not that big grid.

But there always a way, I suggest you to take some pixel as cell size, like 4x4. Then make sure that you have your shapes fill whole space of any cell on which they are resting, like if you have a sqare the make sure it will occupy 2x2 cells completely not 1.5x1.5 cells. This will eliminate the point of getting into possition where you have path passable of only 1 pixel. I know this will make things look very rough on surface but graphics might make it look better.

And the same grid system can be used for collision detection. I useually use 2 pass collision detection, in which first I check for objects very lightly, not counting pixel by pixel, and if found any then go ahead and find whether we have any pixel colliding or not. Grid and Linq make it simple to find collisions for first pass.

Wednesday, August 19, 2009 9:53 AM

All replies

•  Just been scooting around online and it looks like the sort of path finding that im doing is basically obsticle avoidance, and there doesnt seem to be much on this area that i can see, but after seeing some similar sort of problems i could possibly do some sort of quadtree based division of the areas. So rather than having 1 solid size for each path node it would be one overall node of a certain size then it can break down into smaller ones, but im just thinking off top of my head and dont have a clue how i could implement something like that...

Wednesday, August 19, 2009 6:43 AM
• Can't you do something like this: have a grid based system, and on each move of objects update the grid using the size(height and width) and current location of that object from top left. Now you know where the objects are and what path you can take with avoiding collision. Another problem may arise is the moving objects while you travel on the path. For this you have to calculate the path again using the new grid values. I know this is very processor intensive but if you make large grid size you might get better performance. And if you do not want to loose precision with the larger grid size, then you can use 2 pass method, in which first you use large size and then each cell is futher divided to smaller cells to get the more accuracy.

Wednesday, August 19, 2009 8:57 AM
•  Hey,

Maybe im misunderstanding, but the problem im having is working out how to make up the grid. Should the grid just bit a list of x,y points with a ground state var or something describing if its passable or not...

The areas collision shapes dont move, they are all static its just they are positioned absolutely throughout the area, so you may have a rectangle going from 10,10 with a width/height of 59,64 so in that case with an area that is 0,0,100,100 how would you split it out into searchable nodes.

I may have some really big areas, but as its all split in quad trees it is only displayed as and when is needed, so you could have an area > 50000x50000 pixels (when rasterized) so i cant make 50000x50000 path nodes, which is where im not too sure how to split it all out...

Wednesday, August 19, 2009 9:07 AM
• Yes, you can't go with 50k by 50k grid. You have to take some raster value like 4x4 pixel cell or something like that. Then have to traverse through the outer boundary which in tern determine which grid's cell you have to mark out as immovable. Also you can use some algo which has panelty based movement to further enhance the path movement. Some discussion are here on related topic.

What type of object you have, is it of known shapes or irregular polygons? If they are shapes then you can easily determine which grid cells you have to mark as occupied otherwise need to have some maths in your pocket.

Wednesday, August 19, 2009 9:25 AM
•  Primarily rectangles, however there is support for polygons and circles. It uses a custom shape library that exposes Rectangle, Circle, Polygon based collision handlers, that all expose a contains(point) and Intersects(collisionhandler). Although not all are fully implemented at the moment...

My current plan is to make a quadtree containing all the shapes, then every pixel of movement (or something similar) check if the given point is located within a collision tree, if it is then it will have a certain penalty applied if its not then its completely passable. Also that way im only allocating data for the collisions within the tree, rather than allocating a massive grid. Although i still think its going to be pretty inefficient doing it pixel by pixel, but surely thats how all games do it right? As you have to make sure each pixel is passable, if you do it any higher (like 4x4 as you mentioned) you will come accross places where they contain 1 impassable pixel and that would mean you would have to work out if they would acctually touch that 1 pixel or not...

Wednesday, August 19, 2009 9:42 AM
• If you make pixel perfect path then it will not lead to anywhere other than performance bottleneck. I don't know about the quadtree but I did used Grids in my previous 2 games and they did quite well, although my requirement is not that big grid.

But there always a way, I suggest you to take some pixel as cell size, like 4x4. Then make sure that you have your shapes fill whole space of any cell on which they are resting, like if you have a sqare the make sure it will occupy 2x2 cells completely not 1.5x1.5 cells. This will eliminate the point of getting into possition where you have path passable of only 1 pixel. I know this will make things look very rough on surface but graphics might make it look better.

And the same grid system can be used for collision detection. I useually use 2 pass collision detection, in which first I check for objects very lightly, not counting pixel by pixel, and if found any then go ahead and find whether we have any pixel colliding or not. Grid and Linq make it simple to find collisions for first pass.

Wednesday, August 19, 2009 9:53 AM