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?
A* tricks for videogame path finding
61–70 of 108 posts
Re: A* tricks for videogame path finding
#62Earlier 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…
Isn’t the standard solution there to pick one of the horses to do the full path while telling the others “try to move along this path, if not possible then as close as possible, otherwise in the average direction of this group of horses” or something similar?
Re: A* tricks for videogame path finding
#63I 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…
A similar long-time bug in Dwarf Fortress: if you have a door or hatch marked as impassable by animals, but a stray tame critter (usually a cat) wants to get through, it will never give up trying to find a path to the other side. This can have a very noticeable effect on your fps, especially if there are several animals all trying to get past the impassable portal.
(Of course, one could argue that it's incredibly realistic behavior for a cat to very insistently demand to get past a closed door. It would be even more realistic if, once the door is finally opened, the cat would immediately change its mind and lose all interest in getting through!)
Re: A* tricks for videogame path finding
#64Some 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…
Im working on a city builder[0] where you can see inside homes. Expanding on point 1...
1. The streets have their own graph, as does each individual building. There's an address book; each building stores the driveway tile connecting to the street graph here.
2. Pathing inside homes uses A*. In order to make this extra fast, I bake the 8-directional egress weights for each tile in the building/yard.
2b. This gets condensed down into a 16-bit bitmask (2 bit chunks, 8 directions) and then stored in a hash table
2c. Each bit-chunk has four possible states:
FULL_BLOCK (e.g. a wall)
HARD_BLOCK (e.g. a large object that prevents walking through the tile from any direction)
SOFT_BLOCK (e.g. a smaller object that prevents passage on one edge)
NO_BLOCK (e.g. an unoccupied tile, or a tile with a tiny object)
This way a unit pathing inside a building does not need to check for obstacles on every tile. This also allows units to pass through tiles with objects provided the object is not huge and is rotated in such a way that the exit and entrance edge is not blocked. Lastly, an agent can still walk through a wall if the player e.g. forgot to place a door, to prevent the simulation from breaking down.
3. I use a waypoint system (stored in a queue) for agents so they can traverse through the different graph hierarchies with ease. This is also used to e.g. tell the unit to walk to their car first if they are driving.
4. Pathing on the street uses a different method (though still utilizes a baked graph) that makes it extra zippy.
[0] https://store.steampowered.com/app/2287430/Metropolis_1998/
Re: A* tricks for videogame path finding
#65Earlier 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.
Well pathing in sc2 improved significantly, although some problems remain (ultralisks dieing before reaching their target).
In the case of SC1, the dragoon in particular was really bad because its speed would change significantly depending on which part of the animation it was in. That’s what made wheeled vehicles and tanks were less wonky. Their speed was constant as they moved.
Re: A* tricks for videogame path finding
#66One neat pathfinding trick that I use for an in game GPS is to allow the user to specify multiple destinations and find the closest one. Rather than just running it multiple times, I temporarily add a synthetic node to each of the destinations and path to the synthetic node and then look at the previous node to figure out which one to go to.
Are there better ways?
Re: A* tricks for videogame path finding
#67Earlier quoted context omitted.
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.
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.
Re: A* tricks for videogame path finding
#68Some 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…
Songs of Syx is a very performant game that uses 1. I believe, not 100% sure though. It's like Dwarf Fortress but with 100 of times more amount of map actors.
Re: A* tricks for videogame path finding
#69Some 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.
nearest object can be dynamic thing
Re: A* tricks for videogame path finding
#70Earlier quoted context omitted.
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.
nearest object can be dynamic thing
Yes, though many systems make a distinction between fixed objects (like level geometry) and moveable stuff.
If you are inside the bubble, you can disable collision with the fixed objects, and only check for the moveables.
In old-school terms that's background vs sprites.