Questions tagged [path-finding]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
29 views

Box collisions between vehicles in traffic pattern

I'm working on a traffic simulator. Right now, I have ways to manage 4-way stop intersections and a solution for efficiently determining which vehicles are colliding with one another. All vehicles ...
4
votes
4answers
187 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 ...
0
votes
0answers
33 views

Simple stupid funnel algorithm without visible points

In the simple stupid funnel algorithm we are searching for consecutive portals points, that are tightening the funnel (the angle between the current left and right point decreases). But what when ...
0
votes
1answer
51 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, ...
2
votes
0answers
40 views

Reducing the number of edges in a pathfinder

I've worked out an algorithm for pathfinding in a quite free-form terrain (not constrained to grids), with the limitation that it doesn't allow the moving character to rotate. I'll use it for AABBs so ...
2
votes
1answer
89 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 ...
0
votes
2answers
76 views

Pathfinding With Speed Based Turning Restrictions

I have been working on a path finding project and I’m a bit stuck at the moment. I have an object that can increase or decrease speed, but the faster it moves the larger it’s turn radius is - so a car ...
0
votes
0answers
34 views

Agent stuck with each other

As the title. I have stuck on this: When many agents have same destination, they will be stuck with each other. I want they find a new path as character in the picture a attached below How can i make ...
1
vote
1answer
460 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 ...
2
votes
2answers
91 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 ...
2
votes
1answer
489 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 ...
1
vote
2answers
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 ...
0
votes
1answer
47 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 ...
1
vote
1answer
25 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 ...
2
votes
0answers
45 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 ...
0
votes
2answers
84 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 ...
1
vote
0answers
53 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 ...
2
votes
3answers
219 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 ...
1
vote
2answers
68 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 ...
0
votes
1answer
537 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 ...
0
votes
1answer
29 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'] ] ...
0
votes
1answer
61 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 ...
0
votes
1answer
58 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 ...
3
votes
1answer
102 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 ...
0
votes
0answers
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 ...
6
votes
2answers
739 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 ...
3
votes
1answer
192 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 ...
1
vote
0answers
18 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 ...
1
vote
0answers
57 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 ...
1
vote
0answers
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. ...
0
votes
1answer
71 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 ...
0
votes
0answers
25 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 ...
1
vote
0answers
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 ...
0
votes
0answers
93 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 ...
0
votes
0answers
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 ...
4
votes
3answers
700 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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
197 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 ...
0
votes
0answers
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 ...
4
votes
1answer
203 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 ...
7
votes
3answers
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?
0
votes
0answers
53 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 ...
1
vote
2answers
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" ...
2
votes
1answer
675 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-...
1
vote
1answer
99 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 ...
1
vote
3answers
111 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 ...
0
votes
0answers
29 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 ...
21
votes
3answers
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 ...
0
votes
0answers
139 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 ...

1 2 3 4 5 13