I'm working on my first game right now, and even though it's probably a little too ambitious, I am enjoying it. I'm creating a game with a very large, randomly generated world, tile based, with 'free moving' entities - it's my hope to be able to make each entity travel across the entirity of the world, navigating obstacles in the way. This week I managed to implement A* pathfinding. I even managed to get the thing calculating paths over several cycles, so it wouldn't hurt performance as hard. The problem is, my world is very open, which means that the pathfinding algorithm seems to grow exponentially complex when moving only a small fraction of the distance of the world - meaning it takes forever to find a path. Dividing the map into larger chunks, meaning less nodes for A*, is obviously what I need to do. My concern is, if a node is 4 tiles wide, but a path is 1 tile wide, how do I handle that? How do I know if my big node is really 'passable' when it entirely depends on the smaller map tiles? After reading up on this, the solution it seems lies in quadtrees, unless I'm mistaken. Perhaps I've been working too hard, but I'm having a difficult time visualizing how this will work. My A* implementation is the basic 2D gridview type that checks 8 adjacent squares for their F score. With a quadtree, this goes out the window - how the hell do I check which nodes are adjacent to any given node, given that they are tree-structured, not grid structured like my map? I've been researching as best as I can and I found a very nice

">video on youtube showing the kind of solution I'm looking for, I think. I notice that the creator of the video has used a mixture of large and small squares. This is created from a quadtree, but not not transversed as a quadtree, he has it set-out like a grid which A* can handle easily. How did he do that? How would he have handled the problem of knowing which nodes are adjacent to each other when they can be different sizes? His pathfinding sure looks fast there, but his play area is still relatively small compared to what I'm going for, I assume I'm going to need even bigger nodes, 128, 256, 512 or greater in size, calculating adjacent nodes is a problem I have no idea how to solve. Any thoughts welcome.

Quote: Original post by tentaculat
Dividing the map into larger chunks, meaning less nodes for A*, is obviously what I need to do. My concern is, if a node is 4 tiles wide, but a path is 1 tile wide, how do I handle that? How do I know if my big node is really 'passable' when it entirely depends on the smaller map tiles?

What you call the big 'nodes' aren't really nodes as far as A* are concerned. Either you can reach a given node from this node or you can't.

Some people might do hierarchical A*, by plotting a coarse path and then pathfinding within each of the coarse nodes from one side to the other to link them together, but if it's possible to place a barrier within a coarse nodes preventing you from traversing it, then you can't guarantee to find a useful path this way.

Quote: With a quadtree, this goes out the window - how the hell do I check which nodes are adjacent to any given node, given that they are tree-structured, not grid structured like my map?

The adjacency is in the tree. Any node in a tree can ask its parent which are the adjacent nodes (and this may be a recursive operation). A* doesn't care about grids or any layout issues, just which nodes can be reached from which others.

Quote: The problem is, my world is very open

This is only a problem if you approach pathfinding in the wrong way. If you partition your open world up into convex polygons, you can pathfind from one to the next quite easily and efficiently - the more open the world, the better. In fact, with a very open world, you can probably do most of your pathfinding just by drawing a straight line from Start to Goal and doing local repathing or steering wherever you encounter an obstacle.

[Edited by - Kylotan on June 4, 2008 4:57:50 AM]

Sound advice, thank you.

I've got my quadtree working to a certain extent. Like the video I linked in the first post, it will chop the world into quads until it has leaves that are entirely filled with either passable or non-passable tiles, but not mixed. It doesn't take individual tile move costs into account though, but I think I can live with that for now.

So for a 1024 by 1024 area it will give me around 120,000 leaf nodes to use for A*, instead of over a million. I've got those nodes in an 1024x1024 array now, the same as my map region, with every index populated with either a node or a pointer to that node if the that node has a width or height of more than 1, where appropriate.

Now I need to come up with a solution for the following problems:

1) Determining which nodes are adjacent to the current node - I used to check in 1 unit in 8 directions, I can't do that with different sized tiles. I think this is a problem I can solve eventually, though any suggestions would be welcome.

2) Working out the g cost for each node. Before it was pretty easy, I would add 14 for a diagonal adjacent, and 10 for a non-diagonal adjacent. Now a tile could potentially have a lot more than 8 adjacents, if it's large and the adjacent tiles are small.

3) 120,000 nodes is still a lot of nodes for A* and I don't think the quad-tree solution will be enough. A* won't be transversing the quad tree with my current method, only the list of leaves, perhaps there is a way to use the tree structure to A*'s advantage? I've no idea how.

Quote: Original post by tentaculat
3) 120,000 nodes is still a lot of nodes for A* and I don't think the quad-tree solution will be enough. A* won't be transversing the quad tree with my current method, only the list of leaves, perhaps there is a way to use the tree structure to A*'s advantage? I've no idea how.

Usually I advice for using polygonal mesh, but since your game is tile-based, quad-trees make sense.

To answer your questions...

1) You should be able to gather and store all adjacency information as you build the quadtree. Or it should also be possible to dynamically generate all neighbors at runtime, it you store your quandtree properly. When you run A*, getting the adjacent nodes should not depend on the size of the map, only on the number of neighbors.

2) There are a lot of possibilities. For example, you could check where you entered the quad, where you leave it, and calculate a squared euclidian distance. It all depends what you consider to be the navigational edge.

3) 120'000 nodes is not a lot. Games have used A* with millions of nodes in complex environments. Dont get me wrong, reducing the number of nodes is great for performance, but 120k isnt too much to handle if properly coded.

Ok an update.

I've managed to do 1), that is work to out adjacent nodes, at run time as well, though it takes almost a second to complete the entire map. It was easier than I thought, just few nested loops to check the edges of all the nodes. I didn't do it while creating the quadtree, that gave me a headache, though I may revisit that option at a later date for efficiency purposes.

For 2) to calculate g, I just used an absolute value of the sum of the difference between the x and the y of each adjacent node. I'm not sure what the mathematical term for that is, but it works :D

I noticed that A* is running faster now that I have already stored neighbour information for each node, instead of A* working that out. Very nice.

For 3), I think Steadtler is correct that 120,000 nodes is not a lot for A*, but calculating paths across 1000 tiles is still slower than I would like. Since I've managed to overcome what to you guys are probably insignificant challenges, I'm going to work on optimization now.

I'm thinking:

a) Binary heaps for handling the open and closed lists for A*, since sorting those lists appears to eat up most of the cpu time.

b) Using a region system to determine if getting from point A to B is even possible before attempting to use A*. But I want this to be calculable at run-time because I want the world to be destructable, etc.

c) If I steer away from the quadtree shape of the nodes, I can "join up" many of the smaller nodes into bigger nodes to reduce the number. This would be relatively fast, and provided they are still rectangles, I can easily recalculate adjacents.

I felt like I've learned a lot these past few days, though I know I'm not doing things in the optimal way, slowly I think I'm getting somewhere.

The so-called 'closed list' doesn't need sorting. Some sort of hash table for this is best.

Implementation of the open list can be good even when implemented in ways you may expect are poor. eg. insert at end of vector, search the list to find the best, remove it by swapping with the last node and pop it. Being able to use a single chunk of memory, avoiding all sorting, and doing no tree-rebalancing or anything when you pop a node can sometimes mean this works surprisingly well. Sometimes. :)