# Questions tagged [path-finding]

Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.

621 questions
Filter by
Sorted by
Tagged with
83 views

### Correct way to handle A* no pathing?

I'm developing a little game for fun and I wrote a pathfinding system based on the A* algorithm. What is the best or correct way to deal with unavailable paths? A* by default will go through every ...
41 views

### Handling multiple agents in astar pathing

When working with grid based path finding in how do you normally handle different agent types? In the game I am working on I have a regular agent, and one that occupies 2 cells on the grid, and one ...
24 views

### Node representations in a navigation mesh

There are different ways to represent nodes in a navigation mesh. It's either along triangle centroid, along triangle vertices or along edge midpoints. As I understand if you choose triangle centroid ...
44 views

### How can I implement caching into my Rectangular Symmetry Reduction pathfinding algorithm?

I have a working implementation of Rectangular Symmetry Reduction (see here and here for more information on RSR). I'm interested in further improving performance over raw A* by implementing caching ...
80 views

### How to connect nodes in a star pathfinding for platformer games?

In this thread, it tells that in 2d platformer games, I should pre-define and connect node to find the correct path. But I don't understand how to find the node's children. In my program, I define ...
36 views

### Navigation Mesh, Chunks and Funnel Algorithm

I am building a little RTS-like game as a side project and I am currently working on pathfinding. My approach to pathfinding is heavily inspired by things I saw in the Starcraft II map editor, which ...
218 views

### How can I favour vertical travel before horizontal with my A* path-finding heuristic?

I'm writing an AI of a 'police car' that 'patrols' over a 2d grid. Right now, the patrol car randomly selects a destination, finds a path between it's current intersection and the destination ...
63 views

### How can I improve the performance of my A* pathfinding code?

I'm currently working on implementing A* pathfinding into a little project of mine. My ideal goal is that my game should be able to handle about 1000+ objects without any noticable impact on ...
520 views

### Unity3d turn based navmesh algorithm

I am developing a game in Unity3d. In this game, 2 teams will fight without any human interaction. The fight results must be always the same, if the same teams are the same. This way, I must ...
25 views

### Python path finding

Im making a dungeon crawler in python, and I want to make it so that a certain enemy (only 1) will chase you through the dungeon the map is stored like this: [ ['0','0', '0'], ['0','0', '0'] ] ...
59 views

### Improve the algorithm A *?

Hello, I have a question about algorithm A * ! S : Start. D : Destination. W : Wall. My hero goes from S and the destination is D, W is the walls, my hero can't go in there. If I use the algorithm ...
54 views

### 3D A* Pathfinding Algorithm Help

I want to make a 2D turn-based-strategy board game, so I'll need to give my game some pathfinding logic so that units know how to move from place to place. However, I want my levels to have multiple ...
101 views

### How to find the ideal path done inside a given shape in LibGDX?

I'm trying to make an android/libgdx game in which for every level you have a different shape as a png, and you have to drag your finger inside the shape and try to be as close as the ideal path ...
14 views

### How to find edges along calculated path in a navigation mesh

I have a navigation mesh consisting of triangles. I'm using the center of each triangle as a node for a pathfinding algorithm (A*). I would like to do path straightening with Simple Stupid Funnel ...
731 views

### Aligning pathfinding to the center of tiles?

I'm looking to achieve tile by tile movement in a project I'm working on. I employed the use of the asset Simply A* Path-finding to allow a unit to navigate the terrain. Since the tiles are simply ...
170 views

### Which Pathfinding Algorithm is Best For My Case?

I'm creating a top-down space shooter game where there is no real "map" per say since there is no real terrain, but there are obstacles in the form of asteroids, other ships and a few circular ...
17 views

### Having difficulty integrating flow field with flocking algorithm

I have been tweaking my path-finding in my game for a while now, and it's mostly functional, but there are some major issues that are holding me up. I have a flocking algorithm implemented to help ...
50 views

### RTS Pathfinding without collision between units Options

Ever since I made my units move to a certain location a problem has popped up that of course if I try to make two or more units go to the same place they fight for the same spot. Am I just being ...
52 views

### Most efficient way to recalculate enemy A* path on the fly?

I'm working on implementing a more robust pathfinding algorithm for the enemies in my top-down shooter game, and I have the A* algorithm working, but now I need to decide when to calculate the path. ...
64 views

### Higher order splines for use with pathfinding

In this page, Amit explains that splines can be used to achieve movement on a found path. In the picture below, he explains that: The blue paths use splines, with dark blue being low order ...
23 views

### D* lite optimized: what is wrong in my implementation of Search() function?

I'm trying to implement the D*-Lite pathfinding algorithm, as described in the 2002 article by Koenig and Likhachev for grid-based navgraph. But I stuck with problem. My ComputeShortestPath (in my ...
20 views

### Smoothing long paths with splines

What is the best way to smooth a long path with splines? I first implemented a Bezier curve but then realised that I would have to join a lot of them. I used A* on a weighted grid so I can't use ...
180 views

### 2D Top Down: Can't follow the path accurately

In my game, there are many agents. Agents request a path, then after attaining a path to "goal" they follow the path. However player and many other things in the world can impact their position by ...
91 views

### How can I get a straight path using A*?

How to change A* work so that the path is more like a straight Euclidean distance? I read that you need to break some nodes, but how to implement this? I need heuristic like this: Is such a ...
42 views

### NavMesh - LoS and “Containing”

For a gameserver/backend, I have a navmesh for "walkable" areas in form of points/triangles. Now I want to check every gametick if the client is still in a legit place and if he shots/casts a spell, ...
70 views

### How to Steer a Moving Object Away From Another Object(s)

I'm working with C# in Unity, and I'm making a top-down space shooter game in which there are many different AI-controlled ships flying around. The problem is that these ships often fly on top of one ...
25 views

### Which algorithm for controlling cars on a race track? [duplicate]

I think A* is a good place to start, but since cars cannot move in all directions (they move like cars do, trying to move forward and steer), I was wondering if someone could point me at other ...
629 views

### How to fix cutting corner problem in A-star pathfinding

So this is a problem when doing diagonal jumps (checking diagonal neighbor nodes). In 2d it can be prevented by doing some checks, like if up and right is blocked, don't take up-right neighbor for ...
422 views

### Line of Sight Check Theta* Algorithm

I am looking at implementing the Theta* algorithm in a 2D NavMesh. I have A* working, and I need to add a line of sight check to turn it into Theta*, this seems relatively easy in a uniform grid but a ...
84 views

### Pathfinding: Searching through 3D neighbours given certain parameters C#

I'm currently new to the whole pathfinding thing (and coding in general thing), but I seem to have figured it out. It is 3D pathfinding, working on a 3d array of nodes. Everything works, but my ...
14 views

### Find out remaining distance before utilizing SetPath()

I am currently trying to find out the remaining distance of an object to the target point where I click at. However, CalculatePath() will only have a remaining ...
392 views

### Multi-level 3D grid based pathfinding in Unity

I'm trying to come up with a way to pathfind on multiple levels. See image: The orange walls would be considered a ladder, connecting you to the upper levels. At first I thought of looking at it as ...
1k views

### Pathfiding for groups of agents

How can we refine this path search method to make group movement more elegant? I'm trying to make a RTS-style game, using a 2d tiled gameworld. I have implemented an A* pathfinding algorithm which ...
131 views

### Unity Raycast not detecting layers

I am having problems with layers detection using raycasts. Context: I created a grid to use in a pathfinding algorithm on a 2D plane. I want to implement now different weights according to the layer ...
31 views

### How to check in Unity whether tile B can be reached in a straight line from tile A?

I'm currently trying to smooth out my A* paths based on this article. This is what I want to achieve: But sadly I'm stuck at implementing the Walkable method. I ...
197 views

### Why is my A* algorithm is not taking future obstacles into consideration?

I am fairly new to programming, unity, and game design in general. I am following an old A* unity tutorial by Sebastian Lang and the algorithm he used doesn't seem to be completely accurate in terms ...
3k views

### Path finding in grid for objects that occupy more than one tile

In a grid-based game I am working on, I want to add objects that occupy more than one tile of the grid. Are there any algorithms or techniques to find paths for this kind of objects?
51 views

### Modifying A* pathfinding based on size of moving object [duplicate]

I've implemented basic A* pathfinding in my top-down 2D game, and I'm almost ready to test it, but I thought of something while adding the movement code to my enemies that I think could affect the ...
56 views

### Even tiles wide pathfinding on square based tilemaps?

By editing my A* algorithm as such that: a tile is valid if all of its neighbours are valid (checking this N-1 deep) I can find N wide paths, where N is odd, and my unit just follow the "center" ...
674 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 - http://46dogs.blogspot.com/2009/10/star-pathroute-finding-...
98 views

### A* pathfinding question [duplicate]

I'm trying to get a grasp on the A* pathfinding algorithm. Using the image I attached. If the green square represents the start, and red represents the end. wouldn't the algorithm bring me up ...
108 views

### How do i retrieve individual Tile Information from a tilebased procedural World fast?

I am concerned about performance with my current setup; as I want to expand on it i need to figure out if I might need to change it. Current Setup: The Game/Prototype is similar to Dwarf Fortress or ...
27 views

### How could I calculate the distance between the parent and neighbors node when there is a line of sight between two points?

I have completed my Astar algorithm in Python and now I need to convert it to a Theta star algorithm, I have built my line of sight algorithm below, but when I come to my Theta star algorithm I face ...
7k views

### Efficiently pathfinding many flocking enemies around obstacles

I'm working on trying to improve the pathfinding for my game's enemies. Right now, they basically just constantly move towards the player's exact position by calculating the angle between themselves ...
122 views

### Theta Star algorithm with line of sight

I have finished my A star algorithm and I need to add the work of Theta star to it, but I need to call the line of sight algorithm. I'm working on path planning for a UAV and I have created a grid in ...
5k views

### Pathfinding in multi goal, multi agent environment

I have an environment in which I have multiple agents (a), multiple goals (g) and obstacles (o). ...
92 views

### Infinite Loop in AStar (A*) Algorithm

Alright, so I've run into a problem where when trying to find a path that you cannot reach because it is blocked, it will continually loop and loop and loop (the 'open' list is ALWAYS filled). I ...
39 views

### Optimum Path Finding in Varied Terrain

I'm building a sort of city building sim and would like the ability for people to automatically place roads (or rail) based on a start and end point and for the sim to calculate the optimal route. I ...