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)

8
votes
2answers
1k views

What kind of steering behaviour or logic can I use to get mobiles to surround another?

I'm using path finding in my game to lead a mob to another player (to pursue them). This works to get them overtop of the player, but I want them to stop slightly before their destination (so picking ...
0
votes
2answers
89 views

Algorithm to make entities closely follow one another?

I have a group of entities that I want to follow a leader very closely. A good example would be how the player's soldiers move in Cannon Fodder. Any suggestions for achieving movement like this?
2
votes
1answer
225 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
3answers
189 views

A star pathfinding and discrete/smooth positions

The A* (A-star) algorithm usually represents a path on a grid. Once a path has been found, however, the path looks blocky and is not suited if you move your units with floating point datatypes. Here ...
0
votes
0answers
62 views

Drawing pathmap [Solved]

I am developing an editor for my game and I like to implement something like this (screenshot from wc3 editor): (I need the pathmap) I have one implementation already, I just store in chunk renderer ...
2
votes
1answer
50 views

A* in 2D grid with obstacles in between graph nodes

I am using standard A* (and Jump Point Search) for pathfinding in my 2D game. A map in this game is a simple 2D grid (tile-based). A node (i.e. grid cell) in my map graph can either be blocked or ...
0
votes
1answer
119 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 ...
1
vote
1answer
85 views

Using A*Pathfinding on terrain created by scripts?

I'm looking to use A* Path-finding as a method of navigating my game terrain. Trouble is, my terrain is built upon play using a script and A* grid does not detect this, therefore marking all nodes as ...
0
votes
1answer
43 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. ...
1
vote
1answer
90 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
156 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
138 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
1answer
145 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
96 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 ...
2
votes
1answer
117 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
139 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
83 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
213 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
221 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
286 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
71 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
145 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
142 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
192 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
130 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
137 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
208 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
0answers
118 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
74 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
80 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
100 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
404 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
365 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
53 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
244 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
227 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
121 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
107 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
115 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
424 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
64 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
185 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. ...