Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.

learn more… | top users | synonyms (2)

5
votes
1answer
240 views

Dynamic navigation mesh changes

I'm currently trying to convert from grids to navigation meshes for pathfinding, since grids are either too coarse for accurate navigation, or too fine to be useful for object tracking. While my map ...
4
votes
4answers
1k views

A* algorithm very slow

I have an programming a RTS game (I use XNA with C#). The pathfinding is working fine, except that when it has a lot of node to search in, there is a lag period of one or two seconds, it happens ...
4
votes
1answer
359 views

Help me please to choose proper path-finding algorithm

I am new to game development and just want to ask for advice. I need to know which path-finding algoritm will be suitable for my scenario: Units - any shape. But in most cases rectangles of ...
4
votes
3answers
591 views

Find shortest path to gather items

I have a rectangular grid with obstacles and food items on certain tiles. There are also a few storage bins. Each food item gives 10 food. How can I find the shortest path that will allow me to ...
4
votes
1answer
350 views

How to determine that nodes in Grid Graph are unreachable before applying pathfinding?

I would like to determine accessibility of nodes before applying pathfinding algorithm to Grid Graph. I have a surface with nodes overlayed on it and I would like to somehow determine that nodes ...
4
votes
3answers
891 views

What algorithm to use for path mapping?

I am making a turn based game with tiles, much like Final Fantasy Tactics. I am trying to develop an algorithm for mapping out a list of available tiles to walk on. So for example, I am at (0,0) and ...
4
votes
4answers
318 views

How can I make a character smoothly traverse a list of waypoints?

I want to set up paths for enemy characters in my game to patrol. I'd like to be able to define a list of waypoints and have the enemy follow the path from one point to another, but in a smooth curve. ...
4
votes
1answer
376 views

Path finding in games

I am writing my term paper about Path finding algorithms in games, and i've got a couple of questions, hopefully you people could help me out with those ;) So, i've done a little bit of searching ...
4
votes
2answers
233 views

How would I go about updating my electronic circuit simulator's 'electricity'?

I have made an application which allows the user to place down wires, power sources, and inverters on a virtual circuit board. All connections between tiles are automatic, as shown here: As you ...
4
votes
1answer
1k views

How to do starcraft pathfinding?

I've been trying to figure out how to implement something like the pathfinding in Starcraft 2. I'm not looking for all the sophisticated features like flocking, queueing, etc. In fact I like how in ...
4
votes
2answers
1k views

How to create a thread in XNA for pathfinding?

I am trying to create a separate thread for my enemy's A* pathfinder which will give me a list of points to get to the player. I have placed the thread in the update method of my enemy. However this ...
4
votes
3answers
534 views

Creating the nodes for path finding during run time - more like path making and more

I'm making my 1st game. I'm using javascript as I currently want to learn to make games without needing to learn another language but this is more of a general game dev question. It's a 2d turn-based ...
4
votes
2answers
3k views

How to handle pathfinding on a non-grid/non-node terrain map

I'm not sure if this is even path-finding. All I have is a 3D map that has hills, etc. I'd like the enemy to flock an object, but also walk around other objects. These blocking objects may be added ...
4
votes
3answers
642 views

Pathfinding for a lot of units, mostly random movement

I'm using a uniform cost eight-directional grid as a map, with buildings that represent unpassable terrain - the map tries to simulate a top-down flat city. I'm trying to fill the city with randomly ...
4
votes
2answers
1k views

Which pathfinding algorithm should I use for multiple enemies and tower placement?

I am new to game development and I am developing my first "Tower Defense"-type game. I need a pathfinding algorithm to place my towers and to move enemies. For tower placement case: I want the ...
4
votes
4answers
464 views

How can I make my units follow predetermined paths?

I'm planning my first game and am planning on using the engine set out in Beginning Android Games, as it deals with a load of stuff that is just noise at the moment to me (because I've no real world ...
4
votes
3answers
211 views

Unit turning in navmesh-based pathfinding

I'm working on an RTS game, and I'm using navmeshes for unit pathfinding. I do know how to find a general path within a navmesh, but how do you determine if the unit have enough space to turn? I ...
4
votes
3answers
2k views

Which algorithm used in Advance Wars type turn based games

Has anyone tried to develop, or know of an algorithm such as used in a typical turn based game like Advance Wars, where the number of objects and the number of moves per object may be too large to ...
4
votes
1answer
364 views

How does an AI determine the bearing to follow within a nav mesh?

I've done some reading on nav-meshes, and I understand how to generate a path of polygons to reach a goal. However, what I don't understand is how you determine the bearing to follow within each ...
4
votes
1answer
230 views

How can I test if an object will “fit” during pathfinding?

I'm tinkering around with a 2d game where obstacles are polygons of arbitrary shapes, sizes and locations, and movable entities (players/enemies) can also be of arbitrary sizes. What's a good general ...
4
votes
1answer
116 views

Pathfinding avoid a list of polygon

i'm working on a 2D RTS project, no tile-based map. I have a problem on building map data structure & algorithm for that. I already think of a naive algorithm to solve that. Of course it's very ...
3
votes
6answers
783 views

In what instances would you want to use path-finding algorithms other than A*?

I am familiar with how the common ones technically work (BFS, DFS, Dijkstra, A*) but as far as their realistic benefits I don't quite see the need for them. Considering that, given the right ...
3
votes
1answer
267 views

How do I avoid pathfinding characters getting stuck in corners?

I used A* pathfinding to return a list of Tiles to get from an enemy to the player. After that, I wasn't sure how to actually move the enemy. What I ended up doing was get the first Tile in the path. ...
3
votes
2answers
633 views

How to create wrap-around pathfinding?

I've created a planet and obstacle grid and want to move units through this grid using A* or any other algorithm. The only problem is wrapping. I need a simple example of how to handle this unusual ...
3
votes
3answers
4k views

Pseudo-code examples of A*?

I'm looking for pseudo-code examples of the A* pathfinding algorithm that actually works. I tried plenty of different ones where it's not really clear how to implement them at all times. Keep in mind ...
3
votes
1answer
93 views

How are flow fields different from potential fields?

I've heard of of both flow fields and potential fields for pathfinding in games. They sound similar, but I never see them mentioned in the same contexts. Places that mention one never mention the ...
3
votes
2answers
234 views

How to optimize my A* algorithm

I'm working on a roguelike, and I think my A* algorithm is insufficient. My general algorithm for building the dungeon is: Place rooms Figure out which rooms should connect by a relative ...
3
votes
2answers
463 views

Working with chunks of terrain

Let's take for example that in our game, we divide our world (1000x1000 tiles) into chunks of 100x100 tiles. Each chunk contains its own npcs, traps, players, items, whatever. Now, there comes to my ...
3
votes
3answers
177 views

Astar heuristics closing in on an answer before searching around to find nodes with lower movement costs

I am having some trouble with my A* path finding. everything works fine and the path is always found. However, my game is a open map space strategy game. There are no walls etc to navigate around. ...
3
votes
2answers
467 views

Path-finding algorithms for Polar coordinate based maze?

Following on from my question about moving a sprite in a circle, assuming that you have a maze which is shaped like a a set of circles with holes in them and barriers between them. Location of a ...
3
votes
2answers
531 views

How does Half Life's covering work?

Enemies in this game take cover. AFAIK HL uses some logical decisions for enemy to start searching for cover and to abandon cover, and I am able so far to find them; but how does he find a cover ...
3
votes
1answer
574 views

How can I optimize this flood fill algorithm?

I'm creating a sprite and animation editor like this one. I'm having performance issues with my flood-fill algorithm. Basically, I open an image with the different modules that are part of a frame of ...
3
votes
1answer
149 views

How to create a path-finding compatible road map from user input?

I'm currently working on an agent simulation (inspired by the recent SimCity release). Now, basically I understood how agents work but I do not understand how to put them into context. Agents travel ...
3
votes
1answer
217 views

How can I find all shortest paths using A*?

It is possible for A* Path Finding to return all the shortest paths given a graph/map? For example, given the map below: ----------- --a--X--b-- ----------- The said map can return four (4) ...
3
votes
3answers
574 views

Tool for creating complex paths?

I want to create some fairly complex 2d predefined paths for my AI sprites to follow. I'll need to use curves, splines etc to get the effect I want. Is there a drawing tool out there that will allow ...
3
votes
2answers
799 views

Infinite loop during A* algorithm

The A* algorithm is used by enemies to have a path to the goal. It's working but when sometimes I placed a tower in a grid (randomly) it produces a stack overflow error. The A* algorithm would iterate ...
3
votes
2answers
209 views

A Star pathfinding algorithm, multiple node set optimization

I'm trying to determine if this is an optimization I should pursue or if this is way to complicated to be worth my time. I've successfully implemented the A Star Algorithm for my video game. I used ...
3
votes
2answers
327 views

How Does Ultima 7 manage different floors in 2d

In U7, you can move among floors without the function "tranport" the player to another place, as for example the first ff ones. How can it tell whenever the character is moving from floor z to ...
3
votes
1answer
470 views

How do you construct a node map for pathfinding in a non-tiled 2D environment? [duplicate]

A* and Dijkstra's pathfinding algorithms work by navigating a node map. In a tile-based 2D environment, these nodes could easily be inferred to be the literal x,y positions of the map. For example, ...
3
votes
1answer
197 views

Pathfiding for groups of agents

How can we refine this path search method to make group movement more elegant? I'm trying to make a RTS-style game, using a 2d tiled gameworld. I have implemented an A* pathfinding algorithm which ...
3
votes
4answers
1k views

Efficient path-finding on 2D tile-based multilevel map

It's a question I've been thinking about for some time... How do you effiently find a path on a 2D tile-based multilevel map? The map I use, for example, is 2048 on 2048 tiles wide. It has 14 levels ...
3
votes
3answers
551 views

Group arrival steering

I've got group movement implemented pretty much like this: http://www.red3d.com/cwr/steer/CrowdPath.html Basically, that's combining path following and separation. It works nicely as long as units ...
3
votes
1answer
73 views

How to achieve partial pathfinding?

Let's say I already have an A* algorithm. How can I handle the cases when the goal cannot be reached, and still attempt to get there? For instance on the following example: Notice the amazing GIMP ...
3
votes
1answer
2k views

A* pathfinding for an isometric map

I am making an isometric tower defense game in XNA and trying to implement the A* pathfinding algorithms for my enemy AI. I am quite new to programming, especially AI and pathfinding, so please excuse ...
3
votes
1answer
622 views

A* PathFinding Poor Performance

I'm getting poor performance in-game due to my path-finding algorithm. The farther I get from my NPC, the worse the framerate gets. Ok, I updated my code and implemented the openList as a min-heap ...
3
votes
1answer
154 views

Constrained A* problem

I've got a little problem with an A* algorithm that I need to Constrained a little bit. Basically : I use an A* to find the shortest path between 2 randomly placed room in 3D space, and then build a ...
3
votes
1answer
237 views

How can I choose a pathfinding target for a unit group and move the group to that target?

So I've got some units which should move to a specific position which is given by the player. Currently the units can move there by finding a path with the A* algorithm (to be more precise: A* ...
3
votes
1answer
262 views

Verify which bubble is connected to top using DFS

I am working on a bubble shooter game in this game i have implemented searching using DFS as suggested in this link, and this is working fine. Update Here is my code for DFS ...
3
votes
1answer
976 views

How to play character animation when using A* pathfinding

Hi I am trying to make racing game. In which I am using mecanim animation system to animate my character. Here are the conditions for the animation to play Speed --> 1 Run Speed --> ...
3
votes
2answers
213 views

Walk to nearest attackable range node

My game has 3D environment which is partitioned in 2d cells(nodes). I have implemented A* for path finding. Now I am just breaking my head to how to implement the algorithm to move the hero to the ...