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

81–90 of 108 posts

Re: A* tricks for videogame path finding

#81

Post by oasisaimlessly »

moffkalast wrote: post #36
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.

I would put money on a lot of these tricks first being used in games and then being 'rediscovered' by the robotics field.

Re: A* tricks for videogame path finding

#82

Post by Log_out_ »

moffkalast wrote: post #36
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.

We auto devalue everything a human can do as easy. Navigation is a given soon after walking. It's so easy a animal or child can do it intuitively. Until they can't and there are traffic jams.

My personal recommendation is flow field and ROAM. Works excellent for the spring engine

Re: A* tricks for videogame path finding

#83

Post by hypercube33 »

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.

Funny you bring up CNC - OpenRA immediately came to mind for it's horrid pathfinding code that trips itself up when units start crossing bridges and things like that causing units to immediately reroute around the map instead of realizing that the bridge will clear since those units are in motion - red alert 2 at least dealt with this far better but I'm not where near smart enough to figure out how to write code to fix that type of problem.

Re: A* tricks for videogame path finding

#84

Post by moffkalast »

oasisaimlessly wrote: post #81
moffkalast wrote: post #36

Earlier quoted context omitted.

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.

I would put money on a lot of these tricks first being used in games and then being 'rediscovered' by the robotics field.

Almost on a daily basis I would imagine, yep.

Re: A* tricks for videogame path finding

#85

Post by KptMarchewa »

chii wrote: post #67
KptMarchewa wrote: post #60

Earlier quoted context omitted.

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

Which is incidentally what made SC the high skill ceiling it has. If the pathing of SC had been "great", the game mightn't have taken off the way it did competitively.

Eh, there's more to it, the pathing has been one of maybe dozen components that came together like that.

There were more important factors, like having the limit to 12 units in a group - any more would make Zerg much more powerful - now Zerglings are easy to use en masse. Terran bio would benefit from it as well.

Re: A* tricks for videogame path finding

#86

Post by criddell »

Cogito wrote: post #73
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.

How were you storing direction? Was it a symbol for one of NORTH, EAST, SOUTH, WEST, or a symbol for one of FORWARD, LEFT, RIGHT, or a pair of values for row direction and column direction (i.e. +1, 0 or -1, 0 or 0, +1, or 0, -1)?

Re: A* tricks for videogame path finding

#87

Post by Cogito »

criddell wrote: post #86
Cogito wrote: post #73

Earlier quoted context omitted.

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.

How were you storing direction? Was it a symbol for one of NORTH, EAST, SOUTH, WEST, or a symbol for one of FORWARD, LEFT, RIGHT, or a pair of values for row direction and column direction (i.e. +1, 0 or -1, 0 or 0, +1, or 0, -1)?

A tuple vector with row and column offset, your third option here, which happen to have symbol names of N, S, E, and W.

Re: A* tricks for videogame path finding

#90

Post by criddell »

Cogito wrote: post #87
criddell wrote: post #86

Earlier quoted context omitted.

How were you storing direction? Was it a symbol for one of NORTH, EAST, SOUTH, WEST, or a symbol for one of FORWARD, LEFT, RIGHT, or a pair of values for row direction and column direction (i.e. +1, 0 or -1, 0 or 0, +1, or 0, -1)?

A tuple vector with row and column offset, your third option here, which happen to have symbol names of N, S, E, and W.

Thanks for replying. Maybe I just have a dumb bug in my logic and should take another crack at it.
Post reply on HN