Not that I know of, but Imageshack will be willing to help [grin].
Question on path generated from AStar
Author
Quote:Original post by diablos_blade
Not that I know of, but Imageshack will be willing to help [grin].
here it comes,
Link
Thanks
Jack
Oh I see your problem now. Technically speaking string pulling could fix your problem. But it would need the more expensive version. e.g. (assuming I've understood it correctly):
But you're probably better off with a better hueristic in this case. I can't help you with that one though, I've just stuck to the basic geometric distance myself [grin].
I would also be slightly worried about the "dips" that seem to happen beteen the walls. I'd expect A* to return a straight path there, it depends on how you represent your world though (Hex tiles for example, I would expect this as a result).
Hope that helps.
output_pathi = 0while i is not path.length do outputpath.add( path ) furthest_visible = i for j = i + 1 to path.length do if can_see( path, path[j] ) then furthestVisible = j end end i = furthestVisibleendBut you're probably better off with a better hueristic in this case. I can't help you with that one though, I've just stuck to the basic geometric distance myself [grin].
I would also be slightly worried about the "dips" that seem to happen beteen the walls. I'd expect A* to return a straight path there, it depends on how you represent your world though (Hex tiles for example, I would expect this as a result).
Hope that helps.
Quote:Original post by lucky6969bQuote:Original post by mancubit
as for dynamic obstacles, you could just plan a path from the displaced position to a position on the original path to get back on "track". But thats just a quick idea..
Hmm... hope the expense of this splice path (partial path replan) won't be too expensive. I have about 20+ mobile agents on the map... let me try ;)
Thanks
Jack
not really - but maybe this helps you
http://theory.stanford.edu/~amitp/GameProgramming/
Author
Quote:Original post by mancubitQuote:Original post by lucky6969bQuote:Original post by mancubit
as for dynamic obstacles, you could just plan a path from the displaced position to a position on the original path to get back on "track". But thats just a quick idea..
Hmm... hope the expense of this splice path (partial path replan) won't be too expensive. I have about 20+ mobile agents on the map... let me try ;)
Thanks
Jack
not really - but maybe this helps you
http://theory.stanford.edu/~amitp/GameProgramming/
Just a matter of coincidence, I was also taking a look at that page just a few mins ago...
Thanks
Jack
Author
Quote:Original post by inferno82
it will depend on your heuristic, but if you use the general Euclidean distance heuristic, then the behavior you have is expected. The basic algorithm has no concept of space and simply tries to find the optimal path (shortest) to the goal location.
you can of course add in constraints to your neighbor function to require that there be a certain amount of space on each side of a node in order to use that node. This would take into account the unit's width and ensure there would be no collision with the wall.
it all comes down to how you define your heuristic and neighbor function.
- me
Hi Inferno82,
I am actually using the Manhattan Heuristic which looks like
temp->h = abs(dx-sx) + abs(dy-sy);which results in the path I obtained in the picture I posted above(previous post).I find this is extremely fast but sometimes bumps into narrow gaps and the pathfinder decides to get in there. I am looking into ways to walk the path with certain granularity when I take object width into account, but would that be pathetically slow? The thing that really baffles/worries me is the number of objects that need to path-find and how they might get into each other's way... and have to resolve many times over... which creates a bottleneck in my system.
Any comments?
Thanks
Jack
The way I have gone about this in the past to to modify the neighbor function to check to see if a node is indeed passable based on the units width. There are varying ways to do this, a common approach is to use the brushfire algorithm. A good article covering this can be found here.
Basically, you can preprocess the grid offline and determine the distance to the closest object for each cell. Then during your A* search you only consider cells with a distance greater than or equal to the unit's width. This ensures any path generated by A* is indeed okay for the unit to use.
You could also do this online, and for a candidate cell perform a micro search around the cell based on the unit's width and only consider the cell if there are no objects within the unit's width. Obviously, there is an added cost to doing it online.
- me
Basically, you can preprocess the grid offline and determine the distance to the closest object for each cell. Then during your A* search you only consider cells with a distance greater than or equal to the unit's width. This ensures any path generated by A* is indeed okay for the unit to use.
You could also do this online, and for a candidate cell perform a micro search around the cell based on the unit's width and only consider the cell if there are no objects within the unit's width. Obviously, there is an added cost to doing it online.
- me
Author
Quote:Original post by inferno82
The way I have gone about this in the past to to modify the neighbor function to check to see if a node is indeed passable based on the units width. There are varying ways to do this, a common approach is to use the brushfire algorithm. A good article covering this can be found here.
Basically, you can preprocess the grid offline and determine the distance to the closest object for each cell. Then during your A* search you only consider cells with a distance greater than or equal to the unit's width. This ensures any path generated by A* is indeed okay for the unit to use.
You could also do this online, and for a candidate cell perform a micro search around the cell based on the unit's width and only consider the cell if there are no objects within the unit's width. Obviously, there is an added cost to doing it online.
- me
Hi
I am wondering if this is the well-known method that expands the obstacles outwards with a few units, so that the pathfinder can take the width of the agent into account?
Thanks
Jack
This is kind of unrelated, but the the way your paths tend to follow diagonals there is typically an indication that the "actual" path cost that you're using is incorrect. Remember, if you follow a straight line, add 1 to the actual cost for the path, if you follow a diagonal, add sqrt(2) to the actual cost.
Author
Quote:Original post by Codeka
This is kind of unrelated, but the the way your paths tend to follow diagonals there is typically an indication that the "actual" path cost that you're using is incorrect. Remember, if you follow a straight line, add 1 to the actual cost for the path, if you follow a diagonal, add sqrt(2) to the actual cost.
:) Yeah.... something wrong in the cost function... I made a stub for it and forgot to fill it back later on. So all directions cost only 1.., rather than 1.414
:)
Jack
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
