Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.
9
votes
2answers
518 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
132 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
274 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 ...
33
votes
4answers
871 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
230 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
97 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
101 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.
0
votes
0answers
453 views
Collision detection when pathfinding with pathnodes, UDK
I'm trying to create a class that allows my AIController to path find using pathnodes (NOT NavMeshes).
It's doing a swell job of going from point to point in a set order (although I would like for it ...
6
votes
2answers
290 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 ...
3
votes
1answer
181 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 ...
0
votes
0answers
121 views
Restricted pathfinding Area
So i'm triying to create a little "XCOM : Enemy Unknown" like game ,and using the Aron Granberg's
Pathfinding-Tool (free version) to handle the "click to move part.
i want to add a little trap system ...
5
votes
1answer
614 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
581 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
293 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
194 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 ...
-1
votes
1answer
378 views
Javascript A* path finding ENEMY MOVEMENT in 3D environment [closed]
iam trying to implement pathfinding algorithm using PATHFINDING.JS in 3D world using webgl.
iam have made a matrix of 200x200. and placed my enemy(swat) in it .iam confused in implmenting the ...
2
votes
1answer
110 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
344 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
479 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
397 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
225 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
454 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
1answer
585 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
530 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
207 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
votes
1answer
288 views
a* path finding and movement (keeping the character central) [closed]
Now I've built games in xna so I think I'll be ok with the framework mono touch, but I've only ever worked on really simple games in xna so I need to ask a few questions that will help me get started:
...
1
vote
0answers
202 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
47
votes
5answers
6k 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
122 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
302 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
356 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
194 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
850 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
1k 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
2answers
1k 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
951 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
224 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
502 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
819 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 ...
0
votes
1answer
369 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
616 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
222 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 ...
2
votes
2answers
1k 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
221 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
221 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
169 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
344 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 ...
9
votes
2answers
746 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
420 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 ...
3
votes
1answer
4k 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 ...
