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
656 views

Making an AI walk on a NavigationMesh (2D/Top-Down game)

For some time I have been working on a framework which should make it possible to generate 2D levels based on a set of rules specified by level designers. You can read more about it here as I won't go ...
39
votes
4answers
1k views

Pathfinding for fleeing

As you know there are plenty of solutions when you wand to find the best path in a 2-dimensional environment which leads from point A to point B. But how do I calculate a path when an object is at ...
1
vote
2answers
466 views

Influence Maps for Pathfinding?

I'm taking the plunge and am getting into game dev, it's been going well but I've got stuck on a problem. I have a maze that is 100x100 with 0,1 to indicate if its a path or a wall. Within the maze ...
5
votes
1answer
133 views

trapped inside a Graph : Find paths along edges that do not cross any edges

This is a graph based platformer level and the round shapes are creatures. I am looking for a path traveling along edges that does not cross other edges(To simulate the creature crawling on the ...
-4
votes
4answers
124 views

How to select a random node [closed]

I need to know if it is possible to select a random node or select a node itself because I'm doing a zombie AI and I need him to randomly move, and I wanted to know if it's possible to do it and how.
6
votes
2answers
380 views

Best pathfinding for a 2D world made by CPU Perlin Noise, with random start- and destinationpoints?

I have a world made by Perlin Noise. It's created on the CPU for consistency between several devices (yes, I know it takes time - I have my techniques that make it fast enough). Now, in my game you ...
5
votes
1answer
350 views

How can I plot a radius of all reachable points with pathfinding for a Mob?

I am designing a tactical turn based game. The maps are 2d, but do have varying level-layers and blocking objects/terrain. I'm looking for an algorithm for pathfinding which will allow me to show an ...
6
votes
1answer
1k views

2D pathfinding - finding smooth paths

I was trying to implement a simple pathfinding, but the outcome is less satisfactory than what I intended to achieve. The thing is units in games like Starcraft 2 move in all directions whereas units ...
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 ...
5
votes
2answers
600 views

How to create a curve from a set of points that passes through said points?

What is the best way to create a smooth curve path from a set of points? For example: I've seen Bezier curves before, but those try to smooth out the path from the set of points, like this:
3
votes
3answers
528 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 ...
2
votes
1answer
168 views

Is finding graph minors without single node pinch points possible?

Is it possible to robustly find all the graph minors within an arbitrary node graph where the pinch points are generally not single nodes? I have read some other posts on here about how to break up ...
0
votes
3answers
413 views

XNA RTS A* pathfinding issues

I'm starting to develop an RTS game using the XNA framework in C# and am still in the very early prototyping stage. I'm working on the basics. I've got unit selection down and am currently working on ...
7
votes
2answers
598 views

Low CPU/Memory/Memory-bandwith Pathfinding (maybe like in Warcraft 1)

Dijkstra and A* are all nice and popular but what kind of algorithm was used in Warcraft 1 for pathfinding? I remember that the enemy could get trapped in bowl-like caverns which means there were ...
2
votes
1answer
661 views

Pathfinding and BSP with Box2D

I'm looking into implementing AI in my 2D side-scrolling platformer, and I'm looking into using algorithms such as A*. For many kinds of pathfinding, we need some sort of grid or systems of nodes or ...
-2
votes
1answer
416 views

Direction of the bullet - how to have something else than left, right, top, bottom

I'm making a simple shooter game using canvas and javascript. The current code can be seen here. To know which way I want the bullet to be shot, I simply have a direction property that can have 4 ...
7
votes
2answers
1k views

Tweaking AStar to find closest location to unreachable destination

I've implemented AStar in Java and it works ok for an area with obstacles where the chosen destination is reachable. However, when the destination is unreachable, the calculated "path" is in no way ...
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
911 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
312 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
258 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
11k 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
195 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
405 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
693 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
285 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
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 ...
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
375 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
883 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
717 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
775 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
328 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 ...
9
votes
3answers
275 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
348 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
278 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
605 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
615 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 ...
7
votes
1answer
11k 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
271 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
170 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
837 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
582 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
494 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 ...