110
Any system which had a thread for each of so many characters would run out of resources very quickly. Threads may give you access to extra processor cores but they don't make anything intrinsically more efficient, and they come with overhead.
The simple answer is just to be efficient about processing each entity in the game.
Don't process every entity each ...
63
Disclaimer
There are tons of code-examples and explanations of A* to be found online. This question has also received lots of great answers with a lot of useful links. In my answer I'll try to provide an illustrated example of the algorithm, which might be easier to understand than code or descriptions.
Dijkstra's algorithm
To understand A*, I suggest you ...
63
Dwarf Fortress is not open source, and while there is a lot of conjecture and reverse engineering that can go into how that all works, I will instead focus on some basic techniques for optimizing a 3D (not 3D graphics, 3D world) roguelike of the same type.
As is the case with all video games there are a lot of smoke and mirrors that are creating the ...
62
Too many questions at once, so it's hard to give a concrete answer but to discuss a few of these topics. I'll divide the answer in two and try to address it as best as I can. I don't claim any of these lists to be complete, but they're some of the different methods I could remember.
Part 1 - Pathfinding Algorithms
For starters, there are many ways to ...
50
From this page:
Well [the pathfinding] looks amazing from my end, since there's a metric ton of characters all doing it at once.
TA: The dwarves themselves mostly move around with A*, with the regular old street-distance heuristic. The tricky part is that it can't really call A* if they don't know they can get there in advance, or it'll end up ...
answered Jul 23 '12 at 16:53
BlueRaja - Danny Pflughoeft
6,9922 gold badges29 silver badges41 bronze badges
50
This sounds like a use case for Flow Fields.
In this technique, you do a single pathfinding query outward from your player object(s), marking each cell you encounter with the cell you reached it from.
If all your tiles/edges have equal traversal cost, then you can use a simple breadth-first search for this. Otherwise, Dijkstra's algorithm (like A* with no ...
45
Some ideas on avoiding searches that result in failed paths altogether:
Island ID
One of the cheapest ways to effectively finish A* searches faster is to do no searches at all. If the areas are truly impassible by all agents, flood fill each area with a unique Island ID on load (or in the pipeline). When pathfinding check if the Island ID of the origin of ...
43
I've worked on the networking code for two real time AAA networked games, one for smartphones and one for a handheld console.
To directly answer your question "why", well, some games use one or the other because it suits them better than the other. This depends not only on the type of game, but also on what type of network we're talking about (linked arcade ...
34
If you really want your actors to be smart about fleeing, just plain Dijkstra / A* pathfinding won't cut it. The reason for this is that, in order to find the optimal escape path from an enemy, the actor also needs to consider how the enemy will move in pursuit.
The following MS Paint diagram should illustrate a particular situation where using only static ...
33
Climbing, and gaps, are just different cost functions. For a unit that can jump the gap has a normal(?) cost, while for a non-jumping unit it has arbitrarily high cost. Climbing costs extra, as does difficult terrain, etc. The A* algorithm is well able to handle cost functions, so if your implementation is not doing it already, just google for how to ...
31
Yes, the Manhattan distance between two points is always the same, just like the regular distance between them. You can think of the Manhattan distance being the X and Y components of a line running between the two points.
This image (from Wikipedia) illustrates this well:
The green line is the actual distance.
The blue, red and yellow lines all represent ...
28
I wrote flow fields for sup com 2, and I wrote an article explaining the details. It can be found in the upcoming book "Game AI Pro: Collected Wisdom of Game AI Professionals".
Also, I recently did a video stream talking about flow fields for Planetary Annihilation. I show some debug views and explain how it works at a high level.
http://youtu.be/...
27
There are multiple algorithms that are much faster than A* when you need to recalculate a path with moving obstacles. See here under "Simple Recalculations".
However, you're not likely going to find an off-the-shelf solution for any of them, so in 99% of cases they're overkill for a game. Your time would be better-spent using an existing, fully-optimized ...
answered Oct 27 '17 at 18:23
BlueRaja - Danny Pflughoeft
6,9922 gold badges29 silver badges41 bronze badges
26
AStar is a complete planning algorithm, meaning if there exists a path to the node, AStar is guaranteed to find it. Consequently, it must check every path out of the start node before it can decide the goal node is unreachable. This is very undesirable when you have too many nodes.
Ways to mitigate this:
If you know a priori that a node is unreachable (e.g....
24
This might not be the best solution, but it worked for me to create a fleeing AI for this game.
Step 1. Convert your Dijkstra's algorithm to A*. This should be simple by just adding a heuristic, which measures the minimum distance left to the target. This heuristic is added to the distance traveled so far when scoring a node. You should make this change ...
22
I haven't looked at specific implementation of A* by Aaron but with a normal A* you could include the 'block tower' as passable terrain but update the heuristic so that the 'cost' is much higher than a normal tile (so that AI will evaluate whether it is easier to destroy the block and continue or simple go around via the path that is not blocked).
Then you ...
22
Standard pathfinding is Good Enough -- your states are your current location + your current inventory. "moving" is either changing rooms or changing inventory. Not covered in this answer, but not too much additional effort, is writing a good heuristic for A* -- it can really speed up the search by preferring to pick up things over moving away from it, ...
21
A few answers!
The coordinate system I've seen most often for hex-based traversal is one where the player can move in every normal NSEW direction, as well as NW and SE. Then you just render each row half-a-square offset. As an example, the location (2,7) is considered adjacent to (1,7), (3,7), (2,6), (2,8), and the weird ones: (1,6) and (3,8). Meanwhile, if ...
21
Run a dual A* search from the target node in reverse as well at the same time in the same loop and abort both searches as soon as one is found unsolvable
If the target has only 6 tiles accessible around it and the origin has 1002 tiles accessible the search will stop at 6 (dual) iterations.
As soon as one search finds the other's visited nodes you can also ...
20
Keep track of the node with the lowest EstimatedDistanceToEnd (ie. the lowest h(x)), and if no end-node is reachable to backtrack from, backtrack from that node instead.
answered Aug 30 '12 at 13:24
BlueRaja - Danny Pflughoeft
6,9922 gold badges29 silver badges41 bronze badges
19
You should use the D* algorithm, which is designed for this exact scenario. Specifically, the D* Lite implementation is the most efficient and simple variant.
19
The algorithm start with a path you found earlier, in this case a list of triangles:
The code at the bottom of Mikko's blog post constructs the portals array, which is a list of line segments representing the line segments between the path's polygons. These are the "portals" the smoothed path has to go through (or the polygon edges from "let's trace the ...
19
Rather than solving your problem, here's a way to take the lemons and make lemonade.
Many years ago a friend of mine was working on a very well-known FPS which had precisely the problem you describe: a constrained area would have a number of AI characters who had particular desired positions, and the path-finding algorithm was constantly bumping them into ...
18
If anything, it's the opposite - the whole thing runs on one thread and it's now hitting the point where that is becoming the blocking factor (last time I checked!)
The reason it's fast is that there's no fancy graphics. It's deceptive, but the main thing that slows stuff down is drawing things (think upwards of two thirds of a frame in AAA titles). Since ...
18
You can start by letting the pathfinding fail. On failure, choose a random time in the future to re-try pathfinding. Some low level networking protocols work that way, and quite well. What you have to do is build paths one at a time, and mark as used all the tiles an agent will pass through. When further paths fail the random timer to restart will help ...
17
You don't really backtrack.
Think of A* as having an outer “fringe” of nodes that it wants to consider (also called a “frontier”). This is the OPEN set. At every step it picks one of these and expands it, and moves that node into the CLOSED set. The ever-expanding fringe surrounding the start node will eventually eat up the whole map if you let it.
What ...
17
You don't need to adapt A* at all. The only consideration is where you put your nodes and how you connect them. The linked article seems to convert from a platformer-friendly model to a grid based pathfinding model, which I don't think you want.
A* itself is a tree search algorithm which finds the optimal path through your graph and requires some heuristic ...
17
Using a bidirectional path finder usually solves this issue if the area the player is stuck in is small. They basically advance from the player's position and the destination at the same time and when they meet, the algorithm ends. If one of them gets stuck, then you can stop both.
16
Give your agents a weak "electrostatic charge" to make them repel each other, along the lines of Coulomb's law.
Assuming for simplicity that mobs should push each other away with equivalent strength, it should be enough to apply a force between every pair of mobs with a magnitude some_constant / distance^2, where some_constant is a configurable repulsion ...
16
Requirements
You want multiple paths from A to B.
You want to work in grid space, presumably this is tile space for your side-scroller.
You don't want paths to cross, or it will spoil game progression.
You want the paths to look reasonably organic.
Voronoi Diagrams
Voronoi Diagrams are space-filling, planar graphs:
One nice thing about them is how you ...
Only top voted, non community-wiki answers of a minimum length are eligible
