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
2answers
576 views

A* mouse movement javascript top-down game

Im trying to implement a* path finding for my character movement in my game. The game is written in javaScript along with jQuery in a canvas. I have read up on A* so i believe i understand what it ...
14
votes
6answers
1k views

How to make my characters turn smoothy while walking on a path(list of coordinates)?

I have a list with coordinates - output from A* algorithm - and I would like to make my characters smoothly follow this path with rotations. So I have something like A and I want to get C How can ...
3
votes
2answers
469 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
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
178 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. ...
6
votes
1answer
163 views

Complexity of defense AI

I have a non-released game, and currently it's only possible to play with another human being. As the game rules are made up by me, I think it would be great if new players could learn basic game play ...
2
votes
1answer
111 views

Should pathfinder in A* hold closedSet and openedSet or each object should hold its sets?

I am about to implement A* pathfinding algorithm and I wonder how should I implement this - from the point of view of architecture. I have the pathfinder as a class - I think I will instantiate only ...
2
votes
1answer
380 views

Dynamic obstacles avoidance in navigation mesh system

I've built my path finding system with unreal engine, somehow the path finding part works just fine while i can't find a proper way to solve dynamic obstacles avoidance problem. My characters are ...
8
votes
1answer
292 views

Estimating costs in a GOAP system

I'm currently developing a GOAP system in Java. An explanation of GOAP can be found at http://web.media.mit.edu/~jorkin/goap.html. Essentially, it's using A* to plot between Actions that mutate the ...
2
votes
2answers
303 views

What's the best way to move cars along roads

I am implementing car movement game (sort-of like Locomotion). So 60 times a second I have to advance the movement of each car. The problem is I have to look ahead to see if there is a slower car, ...
0
votes
1answer
90 views

Detecting if an object is following a path

I am attempting to take GPS data and track it on a map and see if it follows a given path. I have the path as a set of points and the GPS data streams in as a similar set of points. I am attempting to ...
10
votes
2answers
2k views

Finding shortest path on a hexagonal grid

I'm writing a turn based game that has some simulation elements. One task i'm hung up on currently is with path finding. What I want to do is, each turn, move an ai adventurer one tile closer to his ...
2
votes
2answers
246 views

Prevent collisions between mobs/npcs/units piloted by computer AI : How to avoid mobile obstacles?

Lets says we have character a starting at point A and character b starting at point B. character a is headed to point B and character b is headed to point A. There are several simple ways to find the ...
1
vote
3answers
708 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 ...
42
votes
5answers
2k 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
502 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
140 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
131 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
387 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
376 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
634 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
564 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
176 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
424 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
617 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
681 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
453 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 ...
2
votes
3answers
2k 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
956 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
322 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
266 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
12k 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
203 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
417 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
311 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 ...
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 ...
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 ...
3
votes
1answer
402 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
951 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
816 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
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 ...
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 ...