Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A* tricks for videogame path finding

timmastny.com

Post reply on HN
Print view View original

31–40 of 108 posts

Re: A* tricks for videogame path finding

#31

Post by doophus »

aappleby wrote: post #15

Some tricks I used for A* in a production MMO: 1. Hierarchical graphs: city-level, inter-room in building, intra-room. Allows for navigation from any point in any room in any building in any city to any other point in a fraction of a millisecond. 2. Store metadata about the current a* search in the graph nodes themselves so you don't have to maintain in a separate associative array. 3. Don't follow the resulting path…

> 2. Store metadata about the current a* search in the graph nodes themselves so you don't have to maintain in a separate associative array.

This might be suitable in some circumstances, but it mixes your hot & cold data, prevents concurrent searches from being performed. Personally I'd steer away from this without an extremely good reason.

Re: A* tricks for videogame path finding

#32

Post by 1letterunixname »

urbandw311er wrote: post #13
mysterydip wrote: post #3

Any time A* comes up, someone plugs this great resource: https://www.redblobgames.com/pathfinding/a-star/introduction...

The next big advance after A* is something called [contraction hierarchies]( https://en.m.wikipedia.org/wiki/Contraction_hierarchies ) I’d love to see a “part 2” of this resource or similar that explains those in this kind of Laymans terms. There were some white papers but then I suspect the big tech companies started to guard this research a little more closely once its potential to give a commercial edge became app…

See also Time-Dependent Contraction Hierarchies (2008) [pdf] https://algo2.iti.kit.edu/documents/routeplanning/tch_alenex...

Oh the fun of cobbling heuristic algorithms to work in the real-world where precise algorithms are big-O too slow.

Re: A* tricks for videogame path finding

#33

Post by Arch485 »

dahart wrote: post #14
slowhadoken wrote: post #11

A* is cool but pixel base solutions are naive. Also Dijkstra with a heuristic is just the beginning to a A.I. rabbit hole.

> pixel base solutions are naive. Why, and what do you mean, and what are the alternatives? Pixels are just the search space and may have nothing to do with the sophistication level of the search algorithm, no? In the case of simple 2d games that can run on retro hardware, searching over pixels may be the best thing to do with limited memory and limited cycles, it’s why they often do collision detection on pixels as…

If every tile in the game ("tile" being some discrete unit of walkable/not walkable) is 8px by 8px, then you're doing 64x the work you need to. The tile data will also be stored somewhere anyways to handle player collisions etc. (except in cases where memory is _extremely_ limited, but those are rare - in that case pixel data is used, as you suggested)

Re: A* tricks for videogame path finding

#34

Post by aappleby »

doophus wrote: post #31
aappleby wrote: post #15

Some tricks I used for A* in a production MMO: 1. Hierarchical graphs: city-level, inter-room in building, intra-room. Allows for navigation from any point in any room in any building in any city to any other point in a fraction of a millisecond. 2. Store metadata about the current a* search in the graph nodes themselves so you don't have to maintain in a separate associative array. 3. Don't follow the resulting path…

> 2. Store metadata about the current a* search in the graph nodes themselves so you don't have to maintain in a separate associative array. This might be suitable in some circumstances, but it mixes your hot & cold data, prevents concurrent searches from being performed. Personally I'd steer away from this without an extremely good reason.

Correct, but it was still way faster that way. Pathfinding was already asynchronous (queries happened on another thread so they didn't block any game update loops) and queries were infrequent enough that doing one at a time was fine.

Re: A* tricks for videogame path finding

#35

Post by GuB-42 »

mopierotti wrote: post #19

I've spent a lot of time thinking about fast pathfinding in order to speed up my Scala Quoridor AI*[0], and here are some tips/tricks I've learned: - MPAA (multipath adaptive A*) is great if you need to re-search the same area multiple times as obstacles are introduced. It allows you to feed in the results of previous searches in order to speed up pathfinding. - JPS (jump point search) looks very appealing in theory…

9x9 is a really small grid. 81 tiles. Storing all the distances from every tile to every other tile would take 6561 bytes. Fits in a typical L1 cache.

The nice thing about that is that you can use it as a lookup table for your heuristic function instead of the usual straight line. This table can be initialized at the start of each turn, for example using the Floyd-Warshall algorithm with the already placed walls. I managed to significantly speed up my A* on a similar problem using this technique, plus, it is really simple, it was straight A* though, no MPAA or JPS.

Re: A* tricks for videogame path finding

#36

Post by moffkalast »

aappleby wrote: post #15

Some tricks I used for A* in a production MMO: 1. Hierarchical graphs: city-level, inter-room in building, intra-room. Allows for navigation from any point in any room in any building in any city to any other point in a fraction of a millisecond. 2. Store metadata about the current a* search in the graph nodes themselves so you don't have to maintain in a separate associative array. 3. Don't follow the resulting path…

You know as someone who deals with path planning in robotics where there's a stack of academic papers on each of these concepts, seeing it labelled "tricks" is really funny.

Re: A* tricks for videogame path finding

#37

Post by moffkalast »

dahart wrote: post #14
slowhadoken wrote: post #11

A* is cool but pixel base solutions are naive. Also Dijkstra with a heuristic is just the beginning to a A.I. rabbit hole.

> pixel base solutions are naive. Why, and what do you mean, and what are the alternatives? Pixels are just the search space and may have nothing to do with the sophistication level of the search algorithm, no? In the case of simple 2d games that can run on retro hardware, searching over pixels may be the best thing to do with limited memory and limited cycles, it’s why they often do collision detection on pixels as…

Voronoi graphs are a fast option to get you in the approximate area, then a fine grid can do the last-mile part if need be. It does require preprocessing the map first though.

Re: A* tricks for videogame path finding

#39

Post by whateveracct »

whateveracct wrote: post #38

This article + this HN thread have some nice tricks. I haven't needed A* for much (yet), but I do know there's a nice Haskell library for it https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...

Apparently that's deprecated in favor of monad-dijkstra! https://hackage.haskell.org/package/monad-dijkstra

Re: A* tricks for videogame path finding

#40

Post by dahart »

Arch485 wrote: post #33
dahart wrote: post #14

Earlier quoted context omitted.

> pixel base solutions are naive. Why, and what do you mean, and what are the alternatives? Pixels are just the search space and may have nothing to do with the sophistication level of the search algorithm, no? In the case of simple 2d games that can run on retro hardware, searching over pixels may be the best thing to do with limited memory and limited cycles, it’s why they often do collision detection on pixels as…

If every tile in the game ("tile" being some discrete unit of walkable/not walkable) is 8px by 8px, then you're doing 64x the work you need to. The tile data will also be stored somewhere anyways to handle player collisions etc. (except in cases where memory is _extremely_ limited, but those are rare - in that case pixel data is used, as you suggested)

True, but if players and AI and game elements can move in units of pixels, and exist in multiple tiles at once, the it may be difficult to work in units of tiles. Not clear the parent was distinguishing between pixels and tiles too, or if the ‘naive’ comment was aimed at any kind of gridding, or something else.
Post reply on HN