Tag Info

Hot answers tagged

79

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


45

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


44

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


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


29

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


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


25

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


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


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


16

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


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

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


14

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


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


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.


13

You don't have to search the entire path in one frame, I have done this by giving a limit on the search loop, the AI will then start to follow the little information it has, and the next frame I'll search some more, it might take 3 frames until the path is found. It can look quite convincing to, as it looks like the AI is actually searching.


12

You may already have found this website but I have found it to be a great resource for understanding pathfinding. http://digestingduck.blogspot.com/ The author maintains Recast navigation library. Hope that you find it as useful as I have.


11

It's far from the best, but this an implementation I did of A* in C++ a few years ago. It's probably better that I point you to resources than attempt to explain the entire algorithm. Also, as you read through the wiki article, play with the demo and see if you can visualize how it is working. Leave a comment if you have a specific question. A* on ...


11

D* is quite involved -- I don't recommend trying to implement it. Even when projects that are well funded, and being developed by smart/experienced people, D* lite is used, because D* is such a pain to get right. You may be interested in this presentation, which includes discussion of Left 4 Dead's pathfinding: ...


11

Answer: Rather than calculating a path from one point to another you could calculate the movement direction for each separate tile. Start from the exit, mark each adjacent tile with a pointer to the exit, then from each of these tiles let all adjacent unmarked tiles point to that tile etc. The maths are really the same as Dijkstra's algorithm (A* without ...


11

Make a flood fill from the player's position; every area "flooded" is then a valid play area, and all others are walls. EDIT: As to the "reachable in a straight line" additional requirement, keep in mind that in a discrete space, you have to define this a bit further. For example, all of the paths above could be a valid "straight line" in such an ...



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