6 ms·

It's a very practical optimization (not just a theoretical algorithm) so I don't think it's really misleading in the context of game development. That being sa

by simias 10y ago

It's a very practical optimization (not just a theoretical algorithm) so I don't think it's really misleading in the context of game development. That being said there's an important gotcha, those techniques require a significant amount of precomputations (especially the bounding box one) so it might not be practical if you have very dynamic maps.

Kiro 10y ago
The map in my game is completely dynamic and every pathfinding technique I've tried is way too slow. I've had to resort to a really stupid path finding algorithm where the enemies just looks a few tiles ahead (meaning they get stuck very easily). Any pointers?
- chrisseaton 10y ago
  Are you path-finding every frame? Can you take a snapshot of the game state and run full-path finding on a background core just once every second?
  - Kiro 10y ago
    It's not on every frame but depends on how often the enemy moves (every 150 ms or so). That's a good suggestion anyway!
    - stefs 10y ago
      calculate the path once and cache it. only recalculate it if the agent runs into an obstacle or maybe in a random time interval to make it cheaper.
- dirtyaura 10y ago
  Change your map generation to generate a higher level graph first with ensured paths between nodes and generate subareas so that they connect to higher-level graph?
  - Kiro 10y ago
    Maybe I misunderstood you but the players can change the map during gameplay so I don't think that will work.
    - Elrac 10y ago
      I'm assuming that changes to any given position X on the map happen much less frequently than pathfinding operations that touch on said position X. Is this the case? If so, then investing the pre-calculation effort (updating the precalc matrix, not re-generating the whole thing) at map update time, limited to only those areas potentially benefiting, might be an effective strategy.
    - ProblemFactory 10y ago
      How free-form are the map changes? Do you mean opening and closing doors - or completely changing the terrain as in for example Minecraft? One option would be to look for strategies that "look intelligent", instead of being perfectly optimal paths at every simulation frame. Run slow pathfinding for an enemy and store the path. Have them follow the path until they hit a player-created obstacle, and only then re-run pathfinding. Besides being faster, this could let the players use the enemy behaviour to their advantage by creating traps or such.
    - mikekchar 10y ago
      This may be a naive comment (I know very little about pathing), but one thing I've wanted to experiment with is the idea that enemies shouldn't have perfect pathing when the map changes. I always think, why do enemies know how to get from point A to point B? If they have some knowledge of the map, then you can pre-compute paths, but as the terrain gets modified, those paths will be destroyed. It seems to me that it might be more efficient to modify paths, iterating over the changes in the map rather than iterating over each of the enemies. If locations become unavailable, then "dumb" pathing techniques might be reasonable, possibly using some kind of swarming algorithm, or ant-like behaviour to get around local obstacles.
- dirtyaura 10y ago
  Change your map generation to generate a higher level graph first with ensured paths between nodes and generate subareas so that they connect to higher-level graph?
- triclops200 10y ago
  Look into RRT, it works way too well for how simple it is, and it's great for reducing search complexity for pathfinding.
  - HelloNurse 10y ago
    There's pathfinding and pathfinding. This thread is about exact algorithms for rectangular grids, not approximate algorithms for a continuous space.
    - derefr 10y ago
      There's pathfinding and pathfinding, and then there's pathfinding. Social network analysis also requires route-planning for degree-of-separation computation, but since in those cases you just have a digraph, not a [continuous or discrete] metric space, all you get to use there is Dijkstra. (Anyone who knows better, I'd be delighted to find out I'm wrong—for the sake of my own search runtimes.)
    - triclops200 10y ago
      They're already using a heuristic, I gave them another one to try. It's easy to discretize random samples to a grid.
      - HelloNurse 10y ago
        No, A* heuristics (including extreme ones like jump point search) do not prejudice optimality of the found shortest path, the same that would be found by Dijkstra's algorithm without heuristics. They are only "heuristic" with respect to the subordinate purpose of finding the optimal path cheaply (ignoring as many graph nodes as possible), while the RRT heuristic produces a suboptimal result (not the absolute shortest path, but the shortest path that goes through arbitrarily chosen nodes)
- deleted 10y ago
  [deleted]
- deleted 10y ago
  [deleted]
- justinhj 10y ago
  Is the map dynamic as in it changes in an unpredictable way all the time? If that's the case the best you can do maybe to path find in the static parts then try your best to follow the path while avoiding things nearby. If the map predictably changes between 2 or 3 states you could precompute paths on that and change between them when the map moves.
- yestoallthat 10y ago
  Check out "influence maps" or "potential fields" or "scents" or however they may be called -- google any of those phrases in combination with pathfinding, look at 1-2 videos and you'll grok the idea in a minute, I promise. They may not solve all your problems or even any of them (hard to tell knowing nothing about your game, after all), but I was absolutely dumbfounded when I played around with them at how cheaply you can get some rather complex (seeming) behaviors (e.g. put the player and some enemies in a maze, give the players a scent that strongly attracts the enemies, but also give them a slight scent that makes them repulse each other, and they'll automagically split up and surround the player). At the very least, if you're stuck with what you're doing at the moment, play around with those, and maybe you can at least find a use for them that frees up some processing resources for precise path finding where nothing short of it will do.
  - zamalek 10y ago
    Sometimes also called "flow fields." They are great if your agents are trying to reach a common goal.
  - spiffytech 10y ago
    Have you seen any efficient algorithms that avoid local minima/maxima[0]? All my research leads to either algorithms resembling Dijkstra, or complicated research papers I'm not sure how to implement. [0] Potential fields can't tell you a route is a dead end until you reach the dead end. Then they only tell you you're at a dead end, but don't tell you how to get out and find a viable route. Add-on exit-a-dead-end algorithms I've seen have very inefficient movement. Algorithms to avoid the dead end in the first place have to look ahead so far that you might as well use Dijkstra/A*. ---- Some papers I've turned up: Potential fields: - http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/motion-planning-using-potential-fields-r1125 http://www.gamedev.net/page/resources/_/technical/artificial... - http://www.heikohoffmann.de/htmlthesis/node56.html http://www.heikohoffmann.de/htmlthesis/node56.html - http://www.researchgate.net/publication/222662144_Solving_the_potential_field_local_minimum_problem_using_internal_agent_states http://www.researchgate.net/publication/222662144_Solving_th... - https://randomaccessmaths.wordpress.com/2013/10/27/potential-field-nav/ https://randomaccessmaths.wordpress.com/2013/10/27/potential... Harmonic Potential Functions (related to potential fields, they attempt to solve the local minima/maxima problem) - http://repository.cmu.edu/cgi/viewcontent.cgi?article=1625&context=isr&sei-redir=1 http://repository.cmu.edu/cgi/viewcontent.cgi?article=1625&c... - http://www.itst2007.eurecom.fr/site/var/html/h1053/file1221.pdf http://www.itst2007.eurecom.fr/site/var/html/h1053/file1221.... - http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4295916&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D4295916 http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=429591... - http://ncsu.summon.serialssolutions.com/search?s.cmd=addFacetValueFilters%28ContentType,Magazine+Article%29&s.fvf[]=ContentType,Journal+Article,f&s.fvf[]=ContentType,Conference+Proceeding,f&s.fvf[]=ContentType,Dissertation,f&s.fvf[]=ContentType,Journal+%2F+eJournal,f&s.fvf[]=Language,English,f&s.fvf[]=ContentType,Book+Chapter,f&s.light=t&s.q=harmonic+potential+field+ship+navigation http://ncsu.summon.serialssolutions.com/search?s.cmd=addFace...
- ornitorrincos 10y ago
  I guess you have done it, but have you looked into D* and it's variants? more specifically D-Lite they are A variations for dynamic grids
- jtolmar 10y ago
  Assuming a game with square tiles and vector movement: All shortest paths are either a straight line, or consist of the straight line from the original location to an outside corner, a series of straight lines between outside corners, and a straight line from an outside corner to the destination. (An outside corner is any 2x2 square with three walkable and one wall tile.) You can easily find all the outside corners. You can find which pairs of outside corners can be walked between using N^2 ray casts. Once you've done that, you can detect when an outside corner has been removed and drop it from the map, or detect when one has been created and perform N ray casts to add it to your pathing list. Running A* on the resulting structure is really fast, because it's smaller and more connected than a tile list. The slowest remaining part is finding the corners immediately reachable from your start/end points, which I think could also be sped up but I'd benchmark it before worrying about that.
- adanto6840 10y ago
  How big is your map? If it's still too slow after you've amortized it over a frame or two then I'd guess it's an implementation issue or you're running it too often per entity. At least assuming your graph size is <1000x1000 or so, then the above should generally hold true... That said, flow fields are fantastic tools too.
- taneq 10y ago
  Have you tried probabilistic roadmaps? Depending on how fast the map changes, you might be able to incrementally update a roadmap as you go.
  - bitJericho 10y ago
    Prison Architect has dynamic maps and uses a flow system for path finding escape tunnels. Each grid on the map is simply given a direction telling the ai which way to dig, and its updated periodically. Each tile determines the best direction to direct the Ai and when viewed at a distance looks like a decent pathfinding routine. The benefit of this system is that you can cycle through the map over many frames, not every frame.

by simias 10y ago

Kiro 10y ago

The map in my game is completely dynamic and every pathfinding technique I've tried is way too slow. I've had to resort to a really stupid path finding algorithm where the enemies just looks a few tiles ahead (meaning they get stuck very easily). Any pointers?

chrisseaton 10y ago
Are you path-finding every frame? Can you take a snapshot of the game state and run full-path finding on a background core just once every second?
- Kiro 10y ago
  It's not on every frame but depends on how often the enemy moves (every 150 ms or so). That's a good suggestion anyway!
  - stefs 10y ago
    calculate the path once and cache it. only recalculate it if the agent runs into an obstacle or maybe in a random time interval to make it cheaper.
dirtyaura 10y ago
Change your map generation to generate a higher level graph first with ensured paths between nodes and generate subareas so that they connect to higher-level graph?
- Kiro 10y ago
  Maybe I misunderstood you but the players can change the map during gameplay so I don't think that will work.
  - Elrac 10y ago
    I'm assuming that changes to any given position X on the map happen much less frequently than pathfinding operations that touch on said position X. Is this the case? If so, then investing the pre-calculation effort (updating the precalc matrix, not re-generating the whole thing) at map update time, limited to only those areas potentially benefiting, might be an effective strategy.
  - ProblemFactory 10y ago
    How free-form are the map changes? Do you mean opening and closing doors - or completely changing the terrain as in for example Minecraft? One option would be to look for strategies that "look intelligent", instead of being perfectly optimal paths at every simulation frame. Run slow pathfinding for an enemy and store the path. Have them follow the path until they hit a player-created obstacle, and only then re-run pathfinding. Besides being faster, this could let the players use the enemy behaviour to their advantage by creating traps or such.
  - mikekchar 10y ago
    This may be a naive comment (I know very little about pathing), but one thing I've wanted to experiment with is the idea that enemies shouldn't have perfect pathing when the map changes. I always think, why do enemies know how to get from point A to point B? If they have some knowledge of the map, then you can pre-compute paths, but as the terrain gets modified, those paths will be destroyed. It seems to me that it might be more efficient to modify paths, iterating over the changes in the map rather than iterating over each of the enemies. If locations become unavailable, then "dumb" pathing techniques might be reasonable, possibly using some kind of swarming algorithm, or ant-like behaviour to get around local obstacles.
dirtyaura 10y ago
Change your map generation to generate a higher level graph first with ensured paths between nodes and generate subareas so that they connect to higher-level graph?
triclops200 10y ago
Look into RRT, it works way too well for how simple it is, and it's great for reducing search complexity for pathfinding.
- HelloNurse 10y ago
  There's pathfinding and pathfinding. This thread is about exact algorithms for rectangular grids, not approximate algorithms for a continuous space.
  - derefr 10y ago
    There's pathfinding and pathfinding, and then there's pathfinding. Social network analysis also requires route-planning for degree-of-separation computation, but since in those cases you just have a digraph, not a [continuous or discrete] metric space, all you get to use there is Dijkstra. (Anyone who knows better, I'd be delighted to find out I'm wrong—for the sake of my own search runtimes.)
  - triclops200 10y ago
    They're already using a heuristic, I gave them another one to try. It's easy to discretize random samples to a grid.
    - HelloNurse 10y ago
      No, A* heuristics (including extreme ones like jump point search) do not prejudice optimality of the found shortest path, the same that would be found by Dijkstra's algorithm without heuristics. They are only "heuristic" with respect to the subordinate purpose of finding the optimal path cheaply (ignoring as many graph nodes as possible), while the RRT heuristic produces a suboptimal result (not the absolute shortest path, but the shortest path that goes through arbitrarily chosen nodes)
deleted 10y ago
[deleted]
deleted 10y ago
[deleted]
justinhj 10y ago
Is the map dynamic as in it changes in an unpredictable way all the time? If that's the case the best you can do maybe to path find in the static parts then try your best to follow the path while avoiding things nearby. If the map predictably changes between 2 or 3 states you could precompute paths on that and change between them when the map moves.
yestoallthat 10y ago
Check out "influence maps" or "potential fields" or "scents" or however they may be called -- google any of those phrases in combination with pathfinding, look at 1-2 videos and you'll grok the idea in a minute, I promise. They may not solve all your problems or even any of them (hard to tell knowing nothing about your game, after all), but I was absolutely dumbfounded when I played around with them at how cheaply you can get some rather complex (seeming) behaviors (e.g. put the player and some enemies in a maze, give the players a scent that strongly attracts the enemies, but also give them a slight scent that makes them repulse each other, and they'll automagically split up and surround the player). At the very least, if you're stuck with what you're doing at the moment, play around with those, and maybe you can at least find a use for them that frees up some processing resources for precise path finding where nothing short of it will do.
- zamalek 10y ago
  Sometimes also called "flow fields." They are great if your agents are trying to reach a common goal.
- spiffytech 10y ago
  Have you seen any efficient algorithms that avoid local minima/maxima[0]? All my research leads to either algorithms resembling Dijkstra, or complicated research papers I'm not sure how to implement. [0] Potential fields can't tell you a route is a dead end until you reach the dead end. Then they only tell you you're at a dead end, but don't tell you how to get out and find a viable route. Add-on exit-a-dead-end algorithms I've seen have very inefficient movement. Algorithms to avoid the dead end in the first place have to look ahead so far that you might as well use Dijkstra/A*. ---- Some papers I've turned up: Potential fields: - http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/motion-planning-using-potential-fields-r1125 http://www.gamedev.net/page/resources/_/technical/artificial... - http://www.heikohoffmann.de/htmlthesis/node56.html http://www.heikohoffmann.de/htmlthesis/node56.html - http://www.researchgate.net/publication/222662144_Solving_the_potential_field_local_minimum_problem_using_internal_agent_states http://www.researchgate.net/publication/222662144_Solving_th... - https://randomaccessmaths.wordpress.com/2013/10/27/potential-field-nav/ https://randomaccessmaths.wordpress.com/2013/10/27/potential... Harmonic Potential Functions (related to potential fields, they attempt to solve the local minima/maxima problem) - http://repository.cmu.edu/cgi/viewcontent.cgi?article=1625&context=isr&sei-redir=1 http://repository.cmu.edu/cgi/viewcontent.cgi?article=1625&c... - http://www.itst2007.eurecom.fr/site/var/html/h1053/file1221.pdf http://www.itst2007.eurecom.fr/site/var/html/h1053/file1221.... - http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4295916&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D4295916 http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=429591... - http://ncsu.summon.serialssolutions.com/search?s.cmd=addFacetValueFilters%28ContentType,Magazine+Article%29&s.fvf[]=ContentType,Journal+Article,f&s.fvf[]=ContentType,Conference+Proceeding,f&s.fvf[]=ContentType,Dissertation,f&s.fvf[]=ContentType,Journal+%2F+eJournal,f&s.fvf[]=Language,English,f&s.fvf[]=ContentType,Book+Chapter,f&s.light=t&s.q=harmonic+potential+field+ship+navigation http://ncsu.summon.serialssolutions.com/search?s.cmd=addFace...
ornitorrincos 10y ago
I guess you have done it, but have you looked into D* and it's variants? more specifically D-Lite they are A variations for dynamic grids
jtolmar 10y ago
Assuming a game with square tiles and vector movement: All shortest paths are either a straight line, or consist of the straight line from the original location to an outside corner, a series of straight lines between outside corners, and a straight line from an outside corner to the destination. (An outside corner is any 2x2 square with three walkable and one wall tile.) You can easily find all the outside corners. You can find which pairs of outside corners can be walked between using N^2 ray casts. Once you've done that, you can detect when an outside corner has been removed and drop it from the map, or detect when one has been created and perform N ray casts to add it to your pathing list. Running A* on the resulting structure is really fast, because it's smaller and more connected than a tile list. The slowest remaining part is finding the corners immediately reachable from your start/end points, which I think could also be sped up but I'd benchmark it before worrying about that.
adanto6840 10y ago
How big is your map? If it's still too slow after you've amortized it over a frame or two then I'd guess it's an implementation issue or you're running it too often per entity. At least assuming your graph size is <1000x1000 or so, then the above should generally hold true... That said, flow fields are fantastic tools too.
taneq 10y ago
Have you tried probabilistic roadmaps? Depending on how fast the map changes, you might be able to incrementally update a roadmap as you go.
- bitJericho 10y ago
  Prison Architect has dynamic maps and uses a flow system for path finding escape tunnels. Each grid on the map is simply given a direction telling the ai which way to dig, and its updated periodically. Each tile determines the best direction to direct the Ai and when viewed at a distance looks like a decent pathfinding routine. The benefit of this system is that you can cycle through the map over many frames, not every frame.