A* Question
Author
I was looking up some A* articles for help with my 4E4 game, and I have a little question for you guys. I just read the article A* pathfinding for beginners, and I think I understand the whole A* concept pretty well. Now, it seemed to me that the pathfinding described in that article was designed for a RTS game, where the destination point is static (i.e I clicked here, now go). In my game however, the enemies are going to try and track the players as the player moves throughout the level. If the destination point is not static (the destination being the player), is it really necesary to create a whole path to the destination every time the player moves to another location? What I was thinking of doing was to have the enemies pick only the next node to move to everytime the are updated, so that I still get the A* pathfinding , but without having to compute an entire path everytime the player moves, theywould only have to find the lowest cost square to get to the player. Would this work?
It would depend a bit on the domain that you are applying this to (I'm not sure of the map or environment that you are applying A* to), but would it still work if each enemy only updated their path every second or two? If the enemy is far from the player, it shouldn't make a difference, and you could use a different pathfinding algorithm once the enemies got very close to the player.
Author
The map is tile based, and each tile is about 3 times the size of the player (i.e a tile can be a house and be to scale). Before I would make any pathfinding calculations, I would find the distance to the player and see if the creature could 'see' the player (using a line of sight thing), and if the enemy is within a certain radius, and can see the player, I switch to a simple point and shoot algorithm.
EDIT: added some psuedo-code
EDIT: added some psuedo-code
1) Find starting node2) Find the 8 adjacent nodes3) Discard un-walkable tiles4) Find the movement costs of all remaining nodes5) Find the possible distance to the target node using Manhatten method6) Add movement costs, and distance costs together for remaining nodes7) Find node with lowest total cost8) Retrieve nodes x and y coordinates9) Move to new node and repeat process
Other algorithms are available that build on A* intended for more dynamic worlds, taking into account velocity and acceleration of obstacles and destinations. While continually recomputing the A* path may initially seem like a plausible solution, it could get you into situations where the best path taking into account that the object is moving is actually very different (not to mention possible looping back and forth). For beginners, do a Google search for D* (dynamic A*). Many other options also exist as A* variants.
Do people use the D* algorithm in games, mnansgar? I thought that was more applicable to robotics, where you don't have a starting map at all and need to plan on the fly. Can you implement it efficiently for multi-unit games?
Just curious...
Just curious...
You may want to take a look at RTA*, Real Time A*.
Basically you perform A* with an optimal heuristic for a few iterations, and then increase the heuristic for the rest of the path to speed up the calculation.
This will give you a path really fast with very high accuracy levels.
You may also want to consider using zones, instead of recalculating the path of the enemy everytime the player changes tile, create a big zone, of several tiles, when a player leaves that zone recalculate the path. This carries a few problems though, when you have complex geometry, the case of a wall dividing a zone might happen and give you undesired results, like an enemy that thinks he can reach the player because he is in the same zone when in fact he's separated by a wall. This can be mitigated by carefull creation of those zones, and use of simpler geometry.
Basically you perform A* with an optimal heuristic for a few iterations, and then increase the heuristic for the rest of the path to speed up the calculation.
This will give you a path really fast with very high accuracy levels.
You may also want to consider using zones, instead of recalculating the path of the enemy everytime the player changes tile, create a big zone, of several tiles, when a player leaves that zone recalculate the path. This carries a few problems though, when you have complex geometry, the case of a wall dividing a zone might happen and give you undesired results, like an enemy that thinks he can reach the player because he is in the same zone when in fact he's separated by a wall. This can be mitigated by carefull creation of those zones, and use of simpler geometry.
This is my own little variation (I program path finding for robotic teams a good bit):
Run A* like normal, and get a full path. Then, every other time you run it change the heuristic so that paths near the original are lower cost. I just did this by multiplying all movement withing the "corridor" of the last path by some multiple, like '.95'. The downside of this is that it no longer will find optimal paths, just good ones. What will happen is that while the destination/start point/obstacles move the path will shift over a few runs to take them into account.
Run A* like normal, and get a full path. Then, every other time you run it change the heuristic so that paths near the original are lower cost. I just did this by multiplying all movement withing the "corridor" of the last path by some multiple, like '.95'. The downside of this is that it no longer will find optimal paths, just good ones. What will happen is that while the destination/start point/obstacles move the path will shift over a few runs to take them into account.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement