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

51–60 of 108 posts

Re: A* tricks for videogame path finding

#51

Post by bigbillheck »

GuB-42 wrote: post #35
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 m…

> would take 6561 bytes

3240 if you're nasty.

Re: A* tricks for videogame path finding

#52

Post by justinl33 »

gwillz wrote: post #30

I remember learning A* at uni while at the same time experiencing it's quirks on our shared minecraft server. The server was really chugging and so I ran a trace on it. I found the zombies were stuck in a loop trying to find their way into a village that we had completely secured with a large fence. Being a naive implementation (at the time) it meant they never gave up. I recall there being a bug report with a good a…

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?

Re: A* tricks for videogame path finding

#53

Post by adanto6840 »

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…

One of the more common approaches to AI in games is called GOAP [0][1] (Goal Oriented Action Planning), and it essentially "selects" which action set using the same concept -- graph searching (typically using A*) the available options.

0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...

1 - https://web.archive.org/web/20230804100329/https://alumni.me...

See also (not mine): https://github.com/agoose77/goap-resources

Re: A* tricks for videogame path finding

#54

Post by sojuz151 »

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…

TBH running a full A* for each soldier is not only waistfull but also not realistic. Most people are just moving with the group and might not even know where the entire formation is going

Re: A* tricks for videogame path finding

#55

Post by initplus »

Naive implementations of A* can break down in some common scenarios, with highly connected graphs where many solutions exist. Imagine a long barrier with the start and goal placed on either side at the exact midpoint.

Tie handling is really important! A* is often described as minimizing f(n), where f(n) = g(n) + h(n), g(n) = path distance so far, h(n) = distance to goal heuristic. But for any valid shortest path the remaining work for the algorithm to do is determined by the size of g(n). So when selecting the next node to explore you must minimize first by f(n), and then maximize g(n) as a tiebreaker. Same is achieved by breaking ties with LIFO.

Re: A* tricks for videogame path finding

#56

Post by [deleted] »

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…

[deleted]

Re: A* tricks for videogame path finding

#57

Post by SirMaster »

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…

I don’t know about C&C but in StarCraft units are constantly walking into each other, getting temporarily hung up and stuck a bit.

If they were constantly re-pathing around each other though you would certainly also run into issues too.

Why shouldn’t the units use the information they have about the current destination and path of the other allied units instead of just constantly seeing them as moving obstacles.

Re: A* tricks for videogame path finding

#58

Post by criddell »

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 and it seems to me I should be able to get it work storing cell (as a (row, column) tuple)), direction, and distance travelled (1-3).

If you did this day, how did you do it?

Re: A* tricks for videogame path finding

#59

Post by KptMarchewa »

aappleby wrote: post #34
doophus wrote: post #31

Earlier quoted context omitted.

> 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.

Oh that would be unpleasant if you wanted deterministic behaviour - for example multiplayer RTS.

Re: A* tricks for videogame path finding

#60

Post by KptMarchewa »

SirMaster wrote: post #57
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 don’t know about C&C but in StarCraft units are constantly walking into each other, getting temporarily hung up and stuck a bit. If they were constantly re-pathing around each other though you would certainly also run into issues too. Why shouldn’t the units use the information they have about the current destination and path of the other allied units instead of just constantly seeing them as moving obstacles.

Some of the units in Brood War are legendary due to their bad pathfinding like Dragoon.
Post reply on HN