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)

1
vote
3answers
1k views

Pathfinding library

I'm an amateur game developer and somewhat amateur Java developer as well. I'm trying to find a way to have path finding for my game(s). I've first Googled for some existing Java libraries that have ...
6
votes
2answers
852 views

Creating a navmesh from a voxel terrain

My world is represented by a 3D density field, where a positive density means solid ground and a negative (or zero) density means air. How can I generate a navmesh from that voxel data, with surfaces ...
2
votes
2answers
304 views

jQuery game - collisions

Please take a look at the picture below: It is and attempt in creating a "game" only with the DOM and jQuery. The blue boxes are "obstacles" and the user can move his pointer (not drawn in screen ...
1
vote
0answers
255 views

unity pathfinding [closed]

I have the navmesh and all set up in my unity project but as is I only know how to give it a target to go to, what I want is for it to randomly walk around my scene any help is greatly appreciated
53
votes
5answers
10k views

How does Dwarf Fortress keep track of so many entities without losing performance?

In Dwarf Fortress you can have hundreds of Dwarves, animals, goblins, etc in game at any one time, each with their own complex AI and pathfinding routines. My question is how does this not produce ...
0
votes
1answer
187 views

How can I locate empty space next to polygon regions?

Let's say I have the following area in a top-down map: The circle is the player, the black square is an obstacle, and the grey polygons with red borders are walk-able areas that will be used as a ...
1
vote
1answer
391 views

A* Start path finding in HTML5 Canvas

I'm trying implement A* Start path finding in my games(which are written with JavaScript, HTML5 Canvas). Library for A* Start found this - ...
5
votes
4answers
630 views

Find nearest tile of type x

I currently have an array of tiles which makes up the tilemap (stored as an int array) and I want an NPC to be able to move itself to the nearest tile of type X (ie find the nearest tree and chop it ...
2
votes
3answers
275 views

Discovering path through unknown territory

Let's say all the AI knows about it's surroundings is a pixel-map that it has which clearly shows walkable terrain and obstacles. I want the AI to be able to traverse this terrain until it finds an ...
1
vote
1answer
1k views

A star algorithm implementation problems

I’m having some trouble implementing the A* algorithm in a 2D tile based game. The problem is basically that the algorithm gets stuck when something gets in its direct way (e.g. walls) Note that it ...
4
votes
3answers
3k views

How can I generate a 2d navigation mesh in a dynamic environment at runtime?

So I've grasped how to use A* for path-finding, and I am able to use it on a grid. However, my game world is huge and I have many enemies moving toward the player, which is a moving target, so a grid ...
2
votes
2answers
2k views

How can I better implement A star algorithm with a very large set of nodes?

I'm making a game with nodejs in which many enemies must converge on the player as the player moves around a relatively open space (right now it is an open field with few obstacles, but eventually ...
1
vote
2answers
1k views

Javascript A* path finding

I am trying to learn A* path finding. I am using this library - https://github.com/qiao/PathFinding.js But there is one thing I don't understand how to do. To find a path from player.x/player.y ...
3
votes
1answer
355 views

Fastest pathfinding for static node matrix

I'm programming a route finding routine in VB.NET for an online game I play, and I'm searching for the fastest route finding algorithm for my map type. The game takes place in space, with thousands ...
1
vote
2answers
829 views

Grid pathfinding with a lot of entities

I'd like to explain this problem with a screenshot from a released game, DROD: Gunthro's Epic Blunder, by Caravel Games. The game is turn-based and tile-based. I'm trying to create something very ...
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 ...
1
vote
1answer
662 views

Pathfinding using nodes/waypoints without connecting them?

I've been doing some research on pathfinding lately because I want to code a game modification for a game (won't say which exactly) and what I've done is defined a huge list of 3D vectors where a ...
6
votes
2answers
767 views

Correct way to handle path-finding collision matrix

Here is an example of me utilizing path finding. The red grid represents the grid utilized by my A* library to locate a distance. This picture is only an example, currently it is all calculated on ...
0
votes
2answers
314 views

Tile walking algorithm for already known set of walkable tile?

Suppose I already have a list of tile that specify which tile the character can move to, and these tiles are clustered around the character. If I want to produce a path (maybe not shortest, but just a ...
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 ...
6
votes
2answers
247 views

How to pathfind over an obstacle?

How to represent the following situation best - agent (@) needs to get to the goal($). The path is blocked by a moat(~~~). A rake (or some other device, like waterwalking boots) is available that will ...
4
votes
1answer
339 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 ...
0
votes
3answers
268 views

Logic to path finding checking

I'm a little stuck on the logic to how i use my path finder efficiently in my game. This is basically how the game works: Building generates goods "Factory" > AI transports goods to "Warehouse" ...
1
vote
3answers
583 views

Pathfinding for units of variable size

I'm using a grid map for a top-down RTS, and using a* for pathfinding. Specifically, I've found one implementation which is heavily optimised, and I've been using it for a while, but now I've realised ...
10
votes
2answers
2k views

How do I implement group formations in a 3D RTS?

I managed to get pathfinding work for a single unit, and I managed to avoid agent-agent collision, but now I need to be able to send a group of agents to some location. This is my set-up so far: ...
4
votes
3answers
596 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 ...
6
votes
1answer
10k views

Path finding algorithms?

I posted this question on stack overflow first, but I guess no one is very interested in video games there... What are some path finding algorithms used in games of all types? (Of all types where ...
2
votes
2answers
262 views

Pathfollowing with acceleration - centripetal force

I'm implementing A* waypoint pathfinding with some twists. One of the problems I'm encountering is because I do not change velocities of the agents directly but rather I do so through forces. Which ...
2
votes
2answers
169 views

Grouping units in world space

I figure that I intend to generate, for group orders, one optimal path, and then use a flocking algorithm to "glue" the units together as they all follow this one optimal path. However, a naive ...
2
votes
2answers
795 views

Pointy top hexagonal A* pathfinding

I'm trying to create a game with a hex based map with the points at the top. I have most of it working, however the path finding is being a little awkward. The heuristic I'm using is called euclidian ...
-3
votes
1answer
572 views

c# xna move Image using two Vectors?

initially image placed (0,0)th position and where ever i touch that is end position. Now i got Start Position(0,0) and End Position(200,200). i want to move start to end vector using angle. If ...
2
votes
1answer
479 views

3D RTS pathfinding

I understand the A* algorithm, but I have some trouble doing it in 3D to suit the needs of my RTS Basically, in the game I'm making, there will be agents with different sizes of OBB collision boxes. ...
10
votes
1answer
1k views

Efficient path-finding in free space

I've got a game situated in space, and I'd like to issue movement orders, which requires pathfinding. Now, it's my understanding that A* and such mostly apply to trees, and not empty space which does ...
3
votes
1answer
591 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 ...
6
votes
4answers
2k views

Smoothing found path on grid

I implemented several approaches such as A* and Potential fields for my tower defense game. But I want smooth paths, first I tried to find path on very small grid ( 5x5 pixels per tile) but it is ...
0
votes
1answer
286 views

How do I make A* check all diagonal and orthogonal directions?

I'm making a turn-based tactical game and I'm trying to implement the A* algorithm. I've been following a tutorial and got to this point, but my characters can't move diagonally up and left. Can ...
-1
votes
2answers
289 views

How to spawn a character at certain point and walk to a set point

I am making a game where I have a background image of a neighborhood. Each location has a different number of customers that are generated to walk on sidewalks. They all walk to a specific location ...
4
votes
3answers
487 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 ...
1
vote
1answer
222 views

A* and Space partitioning

I'm planning on implementing A* in my game for pathfinding, I understand the basics of how the algorithm works but I was wondering, other than finding the start and end nodes Are there any benefits to ...
0
votes
1answer
131 views

trouble in making a game questions?

all i've a little trouble understanding some concepts while making game please give your suggestions on my questions. I have a animated sprite image this i want to move this image according to given ...
2
votes
1answer
158 views

Level design: compute minimum time between two items for player traversal

Do any game toolsets offer a means of computing the minimum time it would take a player to move between two objects (or positions, more generally) in a level? I'm not asking about how one would go ...
0
votes
1answer
720 views

A* Pathfinding Problems

I'm trying to implement the a* pathfinding algorithm in my game. I've looked at dozens of tutorials but I can't seem to get it right. My code is below, and It's not working... does anybody see ...
3
votes
2answers
603 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 ...
-4
votes
1answer
336 views

Multidimensional Pathfinding Algorithms

When trying to program hostile AI units for a war strategy game using pathfinder methods, do programmers ever have one algorithm for the unit to move and a separate algorithm for the unit to actively ...
5
votes
3answers
224 views

A* : Partial recalculation when one node *changes*

I have implemented an A* library. Its most interesting feature is that it is "interruptible"; for example, you can stop the calculation loop on a game frame, and resume it later on the following ...
1
vote
2answers
6k views

How can i use A star pathfinding algorithm

How would i implement an A star algorithm for a game that i'm making on the android in java? i'm looking for a pre-made A star API in java with classes and methods to call. i don't want to have to ...
1
vote
1answer
266 views

How can I change the path a sprite is following in real time?

Is there a common way to implement a character following path that is issued and replaced in real time? For example: the character follows a path issued, and while it's on that path, if a new path is ...
5
votes
1answer
325 views

A* pathfinding algorithm to identify entrances into current “room”?

Was looking for some online articles that might have a good idea or two in how to approach this but not finding much. Most of it deals with the various ways to generate and follow a path to a known ...
0
votes
1answer
146 views

Copying section of map array

I'm experimenting a bit with pathfinding. I'm using Javascript. I have a map array as follows: mapArray = [ [0, 0, 0, 1, 1, 0], [1, 0, 0, 1, 0, 0], [0, 1, 0, ...
10
votes
1answer
1k views

Is precomputed pathfinding still relevant?

Context Old Lucas Arts (ScummVM era) point and click graphic adventure games used precomputed pathfinding. Here's a rough outline of the technique. Step 1 The floor in each room was divided into ...