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
1answer
77 views

AI Pathfinding Algorithms

I am looking to create a special kind of pathfinding system. At this point, the geometry is still flexible, but this pathfinding is integral to the project. The goals I have are this: I will have ...
4
votes
1answer
128 views

AI, Pathfinding - Searching Behavior

I'm developing a top-down 2D game mostly based off a tilemap/grid. The player will be able to build structures on this grid while other objects like vehicles will move around freely. I've been working ...
1
vote
2answers
1k views

Is there a way to display navmesh agent path in Unity?

I'm currently making a prototype for a game I plan to develop. As far as I did, I managed to set up the navigation mesh and my navmeshagents. I would like to display the path they are following when ...
4
votes
3answers
125 views

Unit turning in navmesh-based pathfinding

I'm working on an RTS game, and I'm using navmeshes for unit pathfinding. I do know how to find a general path within a navmesh, but how do you determine if the unit have enough space to turn? I ...
0
votes
0answers
22 views

Box2d pathfinding using raytracing / predicted collisions

I have a Box2d/Cocos2d iOS game with enemies that attempt to follow the player (to attack). I'm working on improving the pathfinding logic so that the enemies won't crash into objects in the world. ...
0
votes
1answer
120 views

Smoothing Pathfinding on Tile-Based Terrain but Free-Roaming Player

I'm sorry if this is a long post, but I feel as though the details should help clarify gray areas. I'll try and provide a detailed layout of what I'm trying to achieve, what I have so far, and where ...
0
votes
1answer
91 views

AI / Pathfinding gets stuck

In my tile-based game, I'm using a A-star algorithm, which I have not written myself but I believe should be correctly implemented. The problem I have is that the enemy AI can get stuck so that the ...
0
votes
1answer
94 views

How to follow object on CatmullRomSplines at constant speed (e.g. train and train carriage)?

I have a CatmullRomSpline, and using the very good example at https://github.com/libgdx/libgdx/wiki/Path-interface-%26-Splines I have my object moving at an even pace over the spline. Using a simple ...
2
votes
1answer
109 views

Is it more efficient to use an A* algorithm or a line system drawn in pathfinding in C#?

I was recently introduced to the A* algorithm when I asked a friend about making AI/NPC's in video games move to certain points and it sounded very interesting. I am building an FPS and it has AI that ...
2
votes
2answers
135 views

Pathplanning A* Getting stuck in wall

I'm having a problem with my pathplanning. I can plan a path and make my character follow it, that's not a problem but then i plan a path around a wall it takes the shortest way as A* suggests, which ...
1
vote
1answer
80 views

More Precise PathSmoothing

I'm reading a book about AI - Path planning and path smoothing. Yet this book is using c++ code. And i'm coding in c# with the XNA framework. I have a path smoothing working, yet the book says it can ...
5
votes
1answer
205 views

Dynamic navigation mesh changes

I'm currently trying to convert from grids to navigation meshes for pathfinding, since grids are either too coarse for accurate navigation, or too fine to be useful for object tracking. While my map ...
16
votes
6answers
2k views

How do I make A* agents avoid other agents?

I'm implementing a multi agent A* algorithm on a tile map. Agents move only in the X and Y axes. I avoid collisions between them by checking where the others are when calculating paths. It works fine ...
4
votes
2answers
218 views

How would I go about updating my electronic circuit simulator's 'electricity'?

I have made an application which allows the user to place down wires, power sources, and inverters on a virtual circuit board. All connections between tiles are automatic, as shown here: As you ...
2
votes
2answers
277 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, ...
1
vote
1answer
68 views

Electronic circuit simulator four-way flood-filling issues

I've made an electronic circuit board simulator which has simply 3 types of tiles: wires, power sources, and inverters. Wires connect to anything they touch, other than the sides of inverters; ...
29
votes
4answers
7k views

How does Flow Field pathfinding work?

Supreme Commander 2 has something called flow field path finding. How does it work? Is there some article available I can read up on how it works?
3
votes
1answer
141 views

Constrained A* problem

I've got a little problem with an A* algorithm that I need to Constrained a little bit. Basically : I use an A* to find the shortest path between 2 randomly placed room in 3D space, and then build a ...
0
votes
0answers
12 views

SpriteKit Random Movement/Action [duplicate]

So basically i want a sprite to start from a random position and head to a random direction then take a random turn halfway through using CGPathAddCurveToPoint. The part i fail in is how to make it ...
1
vote
0answers
31 views

Any tips on developing an RTS unit movement collision? [duplicate]

so I am developing an RTS and I am a little stuck at this. I am not talking about pathfinding algorithms like A*. The problem is moving units in bulk and their collision along the way. Can anyone give ...
0
votes
0answers
118 views

SpriteKit Random Action/Movement

So basically i want a sprite to start from a random position and head to a random direction then take a random turn halfway through using CGPathAddCurveToPoint. The part i fail in is how to make it ...
3
votes
1answer
184 views

How can I choose a pathfinding target for a unit group and move the group to that target?

So I've got some units which should move to a specific position which is given by the player. Currently the units can move there by finding a path with the A* algorithm (to be more precise: A* ...
1
vote
2answers
123 views

Unity platform pathfinding

I've been trying to find a way to do this but I'm not sure how. I've gone through A* pathfinding but could find anything on this. What I'm looking for is pathfinding for something kind of like a super ...
0
votes
1answer
100 views

Path finding to collect enough items before the fight with the enemy

So I have the following problem : a X by Y grid. On the grid there is a character and a monster and some items that give bonus points to the character's damage if picked and holes that must be ...
2
votes
1answer
129 views

Detect obstacles in path on a tile-based map

I'm creating a 2d game with a tile-based map, but smooth movement. I currently use A* in combination with some other tricks for pathfinding, and one issue what I've been dealing with is getting the ...
37
votes
11answers
10k views

What path finding algorithms are there? [closed]

I'd like to read up on path finding algorithms. Is there a primer available or any material or tutorials on the Internet that would be a good start for me?
0
votes
2answers
202 views

best way to implement movement after A* pathfinding? tile-based movement vs pixel-based?

I was able to implement the A* pathfinding algorithm to calculate a path from the enemy to player. After trying to do movement well, I realized I ran into all sorts of problems. I was able to add ...
2
votes
1answer
38 views

Moving unit along a computed path

I am generating a path using pathfinding.js. This returns a path of node coordinates from a matrix. Example: var matrix = [[0,0,0,0], //0 are passable, 1 are obstacles [0,1,1,0], ...
2
votes
1answer
184 views

How do I avoid pathfinding characters getting stuck in corners?

I used A* pathfinding to return a list of Tiles to get from an enemy to the player. After that, I wasn't sure how to actually move the enemy. What I ended up doing was get the first Tile in the path. ...
2
votes
0answers
114 views

Simulating crowds of enemies [closed]

I am wondering what would be a good way to handle enemy crowds generation and simulation. For example in a hack'n'slash game, how would one go about placing enemies and managing their movement in the ...
2
votes
2answers
70 views

How can I test if a point is behind a polygon in 2D?

In order to improve the performance of my visibility graph generator I am trying to figure out the following. Given the image below; is there a way to find out if a point is 'behind' the polygon? For ...
2
votes
0answers
77 views

Astar optimalization (A*) [closed]

So I have written own implementation of AStar (A*) algorithm to find paths around my 2d tile based map. My problem is that if I call it each frame (I need to do it) and I'm searching path from corner ...
4
votes
1answer
96 views

Pathfinding avoid a list of polygon

i'm working on a 2D RTS project, no tile-based map. I have a problem on building map data structure & algorithm for that. I already think of a naive algorithm to solve that. Of course it's very ...
6
votes
2answers
389 views

“Line of sight” path across navigation mesh

I want to calculate the line of sight in a navigation mesh. Consider the image below, the yellow line is the result of only A* and the red line is the result of a line of sight" algorithm that uses ...
2
votes
1answer
351 views

Seek Steering Behavior with Target Direction for Group of Fighters

I am implementing steering algorithms with group management for spaceships (fighters). I select a leader and assign the target positions for the other spaceships based on the target position of the ...
0
votes
0answers
50 views

Cane, Recast and detour

I am working with a project which has an implementation of the popular Recast & Detour code. However there is a module of sort called Cane which seem to have to to with the Crowds part, but also ...
0
votes
1answer
237 views

how to implement A Star path finding on 2D map with large tiles

The map tiles I have im my game are 64x64 pixels, and the characters are 16x16 pixels. I was reading about A Star path finding and I was wondering if I need my tiles closer to the size of my ...
7
votes
1answer
220 views

Square Grid Polygonal Terrain Query algorithm?

I have a square, fixed-grid terrain with one terrain type per grid unit in my game, and I want to do an arbitrary polygonal terrain query which returns all of the grid units enclosed/intersected by ...
0
votes
2answers
120 views

Finding the nearest object, considering obstacles

For the purposes of this question, we'll assume it involves a Janitor assigned to clean up trash in a building. Given that it is a building, it is safe to assume there are one or more rooms, walls, ...
2
votes
0answers
103 views

Design Question, Thoughts on Path Finding for a Galaxy Map [closed]

I am thinking through solutions for a galaxy map. We have different solar systems that need to be connected. I do think a-star (A*) is possibly a good solution but was curious if it was really the ...
-2
votes
1answer
112 views

How do I avoid A* pathfinding lists exploding? [closed]

I'm attempting to implement A* pathfinding in my game, and it works for most of the iterations I've tested it with, but I've hit a few random cases where it never stops loading items into the Closed ...
1
vote
2answers
380 views

Pathfinding in non tile-based 2d map (maybe potential field)

I am developing a top-down 2d zombie shooter in AS3. I have implemented collisions against segments (line from point a to point b), polygons (array of points, convex) and round obstacles (center and ...
0
votes
0answers
62 views

Implementing ClearPath (crowd pathfinding)

This is the academic article: http://gamma.cs.unc.edu/CA/ClearPath.pdf Here is the confusing part (marked in red): The first part is the path in which the object will move. The first part of ...
2
votes
2answers
181 views

How can I incorporate the path of a jump into my A* implementation?

I need to calculate the path of a jump via A* for a simple platformer game. Calculating the direction is simple, but translating the jump physics into pre-calcuted voxel paths is a bit difficult. ...
0
votes
1answer
999 views

NavMeshAgent in Unity giving jerky performance

I am using NavMeshAgent in my Unity project to calculate and move my object to a particular location. When I do: navMeshAgent.destination = destinationPt the object starts moving, but the motion ...
3
votes
1answer
231 views

Verify which bubble is connected to top using DFS

I am working on a bubble shooter game in this game i have implemented searching using DFS as suggested in this link, and this is working fine. Update Here is my code for DFS ...
4
votes
4answers
237 views

How can I make a character smoothly traverse a list of waypoints?

I want to set up paths for enemy characters in my game to patrol. I'd like to be able to define a list of waypoints and have the enemy follow the path from one point to another, but in a smooth curve. ...
10
votes
2answers
368 views

How can I compute the shortest path in Euclidean environments with non-convex polygons?

Can someone suggest papers or algorithms about calculating shortest paths in Euclidean spaces with non-convex polygon as obstacles?
0
votes
0answers
305 views

NavMesh agents pushing other NavMesh Agents in Unity Pro

Using the NavMesh system in Unity, I created pathing system for my player character as well as the enemy AI. When a group of enemy NavMesh Agents surround my player character, they can be pushed out ...
5
votes
3answers
145 views

Pathfinding Search for Path of Specific Length

I am creating a roguelike. This question applies to random map generation. First, I generate areas using a BSP algorithm, where I randomly divide the map into areas. Then, I generate a graph of the ...