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)

6
votes
3answers
4k 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 ...
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 ...
1
vote
1answer
418 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
766 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
312 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 ...
2
votes
2answers
3k 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 ...
1
vote
2answers
954 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 ...
6
votes
2answers
793 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 ...
1
vote
1answer
818 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 ...
0
votes
2answers
348 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 ...
4
votes
1answer
367 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
3answers
657 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 ...
0
votes
3answers
302 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
631 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 ...
7
votes
1answer
12k 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 ...
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: ...
2
votes
2answers
281 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
173 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
903 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
627 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 ...
3
votes
1answer
629 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 ...
2
votes
1answer
508 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 ...
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
302 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
311 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 ...
12
votes
1answer
4k views

A* navigational mesh path finding

So I've been making this top down 2D java game in this framework called Greenfoot and I've been working on the AI for the guys you are gonna fight. I want them to be able to move around the world ...
4
votes
3answers
543 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
1answer
346 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 ...
1
vote
1answer
230 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
744 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 ...
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 ...
6
votes
1answer
568 views

Linking nodes algoritm for Visual Design

I'm developing an editor for my game, and now it's time to make a visual scripting system to let designer modify behaviours. This video shows what i have done and the problem to resolve the link ...
2
votes
1answer
160 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 ...
2
votes
3answers
431 views

Best way to implement mouse-based movement in MMOG

I want to design an MMO where players click the destination they want to walk to with their mouse and the character moves there, similar to Runescape in this manner. I think it should be easier than ...
3
votes
5answers
1k views

Pathfinding in multi goal, multi agent environment

I have an environment in which I have multiple agents (a), multiple goals (g) and obstacles (o). . . . a o . . . . . . . o . g . . a . . . . . . . . . . o . . . . o o ...
3
votes
2answers
641 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 ...
5
votes
3answers
225 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
1answer
277 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 ...
2
votes
1answer
1k views

Enemy Movement AI

I have a non-tile-based top down shooter game, and I have enemies set up. However I need the enemies to move to the player. Pathfinding algorithms will mean the enemies will just hug the wall. The map ...
5
votes
1answer
332 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
151 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 ...
9
votes
3answers
3k views

How do you do AI path following within a 2d physics engine like farseer/box2d?

I'm in the process of moving a 2d top down game I've been working on into a proper rigid body physics engine like Farseer. Up until now, I had just hacked together my own physics code where needed. ...
8
votes
2answers
2k views

pathfinding with obstacles in a Warcraft 3 like game

Consider A* searching on a tile based map. A straight forward code would be: If there is an unit inside that cell, then it is unreachable, this is ok. But there is map resolution issue. When I look ...
0
votes
1answer
212 views

Good baseline size for an A* Search grid?

I'm working on a grid based game/prototype with a continuous open map, and are currently considering what size to make each segment. I've seen some articles mention different sizes, but most of them ...
2
votes
4answers
246 views

Path tables or real time searching for AI?

What is the more common practice in commercial games; path lookup tables or real time searches? I've read that in many games path lookup tables are pre-calculated and baked into each map, so to ...