Tag Info

Hot answers tagged

83

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


48

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


46

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


36

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


31

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


30

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


26

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


25

If you're looking to research and learn about pathfinding in general, I'd definitely suggest learning more than just one algorithm. You'll want to understand the overall concepts but be able to apply them to whatever it is you are working on. Most game developers who need to do any serious pathfinding end up writing their own custom algorithms, although ...


25

In most cases, using A* over a navigation mesh (commonly referred to as a "navmesh") is the pathfinding solution commercial RTSs use. There is a detailed explanation of how navmeshes work, why they are a better solution than waypoint systems, and links to implementation resources, here. If you're planning on developing special game modes (point/node ...


23

A* path finding is a best-first type search that uses an additional heuristic. The first thing you need to do is divide up your search area. For this explanation the map is a square grid of tiles, because most 2D games use a grid of tiles and because that's simple to visualize. Note however that the search area can be broken up in any way you want: a hex ...


22

Pathfinding algorithms are basically a graph search problem solving algorithms. http://en.wikipedia.org/wiki/Pathfinding#Algorithms Most known being Djikstra's algorithm: http://en.wikipedia.org/wiki/Dijkstra's_algorithm and its variant A* search algorithm: http://en.wikipedia.org/wiki/A*


19

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


19

In your path scoring just make it so passing through a tower costs the same as going through some big number of tiles. In general it will try to get around them, but if there isn't such a path the output will still be going through the least number of obstacles. You can tune the penalty so that sometimes they will just go through instead of going all the way ...


19

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


18

The main consideration for deciding whether to use square vs hex grids shouldn't be ease of AI implementation -- breadth-first and depth-first search algorithms are pretty much the same no matter what kind of graph you have. Rather, this is a gameplay issue that should be considered by the game designers. Square grids are more accessible to the mass market ...


18

From what I know, you could take a look at the D* algorithm which stands for "Dynamic A*". This algorithm is used to compute pathfinding for dynamic environment, here with a moving target. Here's a paper using D* for moving target path finding : Moving Target D* Lite


17

I've been looking for this term as well, and this paper is the only major one I could find that references flow fields directly: http://www.aaai.org/Papers/AIIDE/2008/AIIDE08-031.pdf This approach involves each pathfinding agent being influenced by a global vector field, and in turn influencing that field with their resulting path. You still need some ...


17

I needed to solve a similar problem: pathfinding on a large maze-like grid with constantly changing "costs" and barriers. The thing is, in tower defense game the number of entities that need to have the path solved for them is usually much larger than the number of nodes in the graph. A* is not the most appropriate algorithm for handling this, because ...


17

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.


16

Steering behaviors are designed for pretty much this exact problem set. http://www.red3d.com/cwr/steer/ Basically you would combine the obstacle avoidance behavior with probably the seek or pursue behavior. That page has a bunch of java animations of the different behaviors and what they do. There are several open source implementations of steering ...


16

Computing just one move sounds like a bad idea to me. If you don't compute the whole path, then you don't know that the next tile to move to is correct, so a lot of the time units will get trapped. Caching the entire path for a unit won't take too much memory. It's just a list of node IDs. The main problem is generating the path in the first place, and how ...


16

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


15

Amit's A* Pages were a good introduction for me. You can find a lot of good visualizations searching for AStar Algorithm on youtube.


15

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


15

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.


14

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


14

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


14

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


13

I'm assuming that TD is 'Tower Defence' I think A* is going somewhat overboard for this. At the start of the game, flood fill the game area from the exit points to create a movement map: |---------| |5|4|3|3|3| |5|4|3|2|2| ->5|4|3|2|1-> |5|4|3|2|2| |5|4|3|3|3| |---------| and movement is always towards a square with a lower value. When the ...


13

Have a look at steering behaviors. Especially seek and arrival might be interesting for your needs. These behaviors will also work when some other influences like an explosion changes the ships position temporarily.



Only top voted, non community-wiki answers of a minimum length are eligible