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

71–80 of 108 posts

Re: A* tricks for videogame path finding

#71

Post by ReactiveJelly »

aappleby wrote: post #25
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…

Oh, and compute the distance from each path node to the nearest obstacle and store that in the path node. As long as your character is inside one of these "bubbles", you can skip collision detection against the world entirely.

Oh like in path tracing.

Re: A* tricks for videogame path finding

#72

Post by eru »

hwillis wrote: post #20
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…

> Hierarchical graphs: city-level, inter-room in building, intra-room. Handmade? It's always annoying to me when you have a small NP-hard problem (graph partitioning is definitely a recurring one for me) and you want to just throw some box algorithm at it without having to shop around for a library that you have to learn. I remember there was a while in college where I didn't understand why A* in an RTS would be such…

Small NP-hard problems aren't actually that bad. You can usually formulate them as eg a integer programming problem or a SMT problem, and throw an off-the-shelf solver at them.

You only need to learn the solver once, and you can re-use it for all kinds of problems. (Assuming that your instances don't have to be solved with low latency. Eg only as part of your level generation process, or at most when loading a randomly generated level, but not every frame or so.)

https://developers.google.com/optimization has a decent collection of tools.

Re: A* tricks for videogame path finding

#73

Post by Cogito »

criddell wrote: post #58

Off topic, but tangentially related: I was trying to use a modified Dijkstra / A* algorithm for this year’s Advent of Code Day 17 problem: https://adventofcode.com/2023/day/17 I never got the right answer though because there was some issue with the way I was tracking visited nodes. I was trying to use north, south, west, east rather than row and column direction values like other solutions I read, but I’m stubborn a…

My search nodes were tuples of position, direction, and steps taken in the same direction.

More or less a straight depth first search with a priority queue from there.

Re: A* tricks for videogame path finding

#74

Post by eru »

superjan wrote: post #24
hwillis wrote: post #20

Earlier quoted context omitted.

> Hierarchical graphs: city-level, inter-room in building, intra-room. Handmade? It's always annoying to me when you have a small NP-hard problem (graph partitioning is definitely a recurring one for me) and you want to just throw some box algorithm at it without having to shop around for a library that you have to learn. I remember there was a while in college where I didn't understand why A* in an RTS would be such…

I have seen an article posted here that did A* on a low resolution versions of the game map, and use the output of that as the heuristic for the full res version. In that design, the low res version was auto generated.

That's nifty, because A* itself is already a two-step process that uses a heuristic. You can blow it up to multiple steps fairly easily.

Re: A* tricks for videogame path finding

#75

Post by keriati1 »

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…

+1 for the bucket queue. I learned about that trick a few weeks ago and in my use cases it cut the time to run A* by around 60-70%.

Re: A* tricks for videogame path finding

#76

Post by throwaway17_17 »

djmips wrote: post #46

An interesting application of A* in a game context was a programmer who was faced with making the Computer opponents of a game in the early 2000s and what he came up with was an abstraction of the options the AI had in the game and used A* to find the closest distance in the graph. I thought it was pretty cool because it wasn't using A* in the traditional way of pathfinding the world but instead pathfinding in a repr…

I think the ability to use similar ‘planning’ algorithms for walking through a room, choosing an option for attack/defend/use item, which enemy to target, may account for some of the attribution of intelligence to game AI. Humans seem to think they and other humans put as much thought and think in similar patterns about wildly dissimilar activities like planning a route or weighting risk/reward or planning an event 6 months out. So the ability to encode a wide variety of ‘search space’ into an appropriate graph for use with a common algorithm lends a perceived verisimilitude to the AI’s thoughtfulness and near-personhood when immersed in play.

Re: A* tricks for videogame path finding

#77

Post by alexey-salmin »

araes wrote: post #29
hwillis wrote: post #20

Earlier quoted context omitted.

> Hierarchical graphs: city-level, inter-room in building, intra-room. Handmade? It's always annoying to me when you have a small NP-hard problem (graph partitioning is definitely a recurring one for me) and you want to just throw some box algorithm at it without having to shop around for a library that you have to learn. I remember there was a while in college where I didn't understand why A* in an RTS would be such…

This is one of the main issues in attempting to build a game like the Total War series. When you start getting into 10,000 unit formations that need to pivot or strafe, while moving around or through other unit groups and obstacles, A* starts being rather challenging. Trying to get 100,000 horses to ford a river reasonably when there's only a relatively small zone of safety can be tough to program. Also, mipmaps towa…

> Trying to get 100,000 horses to ford a river reasonably when there's only a relatively small zone of safety can be tough to program.

I imagine this is also very tough in real life

Re: A* tricks for videogame path finding

#78

Post by Zondartul »

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…

takes notes Fascinating. Any other sage advice on navigation and game-ai?

Re: A* tricks for videogame path finding

#79

Post by justinl33 »

gwillz wrote: post #61
justinl33 wrote: post #52

Earlier quoted context omitted.

Been looking around for the past 10 minutes trying to find information on the mob-following implementation in Minecraft - can't find a thing. I assume it's just vanilla A* with some parameters?

Found it! https://bugs.mojang.com/browse/MC-17630?focusedCommentId=925...

> Since working the (apparently A) pathfinding algorithm...*

Beautiful.

Re: A* tricks for videogame path finding

#80

Post by the_gipsy »

Udo wrote: post #50
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…

Expanding on the "breadcrumbs": pheromone trails or "trampled grass" are awesome, not only because they are a great data source for steering heuristics, but they also lead to organic-seeming navigation behavior that is pleasant to look at.

Usually if something wants to go where something else is, it either want to go in its footsteps or flank it at a point where it predicted to be when both meet.
Post reply on HN