I''m a newbie when it comes to game programming, especially AI. Still, I find it a fascinating topic and would like to learn more about it. It''s definetly something I could get into I think.
Peon
Implementing A*
Author
Having been trying to understand how pathfinding could be done for years, I came across the A* algorithm, and I more or less understand it (on paper) I''m not sure I could code an implementation myself yet, but I think I''m beginning to understand how I could do it.
One question I''ve had is when you would call a pathfinding function. At least to me, it seems too costly to try and call a pahtfinding function using A* everytime you need it; it seems like it would take too much processing power. The only other option I would think of would be to somehow have a precompiled list of all the squares, and their distance to all the others. In this way, you could figure out all the pathfinding before the map is even loaded (ie: when you make the map itself) or maybe at run time, and only load it once.
Is anything like this done? (figuring out pathfinding data in a non real time fashion, like a giant look up table) I read some interesting topic titles which caused me to think that this exists, but unfortunately, I did not understand the content I''m a newbie when it comes to game programming, especially AI. Still, I find it a fascinating topic and would like to learn more about it. It''s definetly something I could get into I think.
Peon
I''m a newbie when it comes to game programming, especially AI. Still, I find it a fascinating topic and would like to learn more about it. It''s definetly something I could get into I think.
Peon
You could make precomputed tables if you don''t have terrain or maps that can be altered during play but it would take a massive amount of memory to store the best paths from each tile to each tile. Storing the distance from a tile to another tile is pretty pointless IMHO.
Having just implemented an A* algorithm and gotten it to work in 800 usec on an AthlonXP 1700+ for a path length of 30 tiles I''m quite confident that I can use it every time a path needs to be found in my own game (which is real-time).
Having just implemented an A* algorithm and gotten it to work in 800 usec on an AthlonXP 1700+ for a path length of 30 tiles I''m quite confident that I can use it every time a path needs to be found in my own game (which is real-time).
If you have dynamic objects that can form obstacles, it''s fairly pointless to do pre-computed pathing. And even when you don''t, it''s almost never worth the effort.
Usually, instead of invoking the full-blown pathing algorithm, there''s a check to see if a straight-line path is open to the destination. If there isn''t, then the pathing algorithm is used.
Some applications do another intermediate step. The map is marked with a series of waypoints, and each waypoint is given the knowledge of the other waypoints that it has line of sight to, in the absense of dynamic objects. When pathing is needed, the search starts with finding the nearest waypoint in line of sight, and then doing a graph traversal along the waypoints to reach the waypoint nearest the destination. Edges between waypoints are removed if line of sight is blocked. The resulting path is sent through a smoothing algorithm. Depending on the complexity of the map and the care with which the waypoints are chosen, this can be much faster than doing A* on the whole map. This is commonly known as hierarchical pathing. (And provided that I spelled hierarchical correctly, you can probably google for it and find more references.)
Usually, instead of invoking the full-blown pathing algorithm, there''s a check to see if a straight-line path is open to the destination. If there isn''t, then the pathing algorithm is used.
Some applications do another intermediate step. The map is marked with a series of waypoints, and each waypoint is given the knowledge of the other waypoints that it has line of sight to, in the absense of dynamic objects. When pathing is needed, the search starts with finding the nearest waypoint in line of sight, and then doing a graph traversal along the waypoints to reach the waypoint nearest the destination. Edges between waypoints are removed if line of sight is blocked. The resulting path is sent through a smoothing algorithm. Depending on the complexity of the map and the care with which the waypoints are chosen, this can be much faster than doing A* on the whole map. This is commonly known as hierarchical pathing. (And provided that I spelled hierarchical correctly, you can probably google for it and find more references.)
If you want to compute and store the pathfinding information for a level you can use Dijkstra''s algorithm to return all shortest paths in a graph structure (in this case, the connectivity graph derived from your map tiles). The algorithm computes the shortest path between all pairs of tiles.
This is though storage intensive. There are better tile-based (discreet state space) pathing algorithms out there.
On the issue of when to call your pathfinding routine, that depends on how you set up your game engine. If you''re up to the task, multi-thread your application so that your AI runs on it''s own thread, with a dedicated amount of CPU time for running that thread. Call you pathfinding whenever it is needed, without fear of it slowing down your frames per second!
Cheers,
Timkin
This is though storage intensive. There are better tile-based (discreet state space) pathing algorithms out there.
On the issue of when to call your pathfinding routine, that depends on how you set up your game engine. If you''re up to the task, multi-thread your application so that your AI runs on it''s own thread, with a dedicated amount of CPU time for running that thread. Call you pathfinding whenever it is needed, without fear of it slowing down your frames per second!
Cheers,
Timkin
In Games Programming Gems 3, there is an article that could be of use to you. It is called "A fast approach to navigation meshes".
It is based on a connected navigation mesh of triangles, where for a given (source, destination) pair, you store which portal (edge of the source triangle) to go through to get one step further. This only requires 2 bits of storage for each pair.
The total memory cost is then (n*n*2) bits, where n is the number of triangles in your nav-mesh. For 256 triangles, this is 16kb. Not too shabby ;-)
If you do all of this offline, the runtime use of the algorithm just involves looking up your values, which should be nice and fast.
Lion
It is based on a connected navigation mesh of triangles, where for a given (source, destination) pair, you store which portal (edge of the source triangle) to go through to get one step further. This only requires 2 bits of storage for each pair.
The total memory cost is then (n*n*2) bits, where n is the number of triangles in your nav-mesh. For 256 triangles, this is 16kb. Not too shabby ;-)
If you do all of this offline, the runtime use of the algorithm just involves looking up your values, which should be nice and fast.
Lion
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
