Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [path-finding]

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

0
votes
0answers
15 views

Jump Point Search on an infinite grid

I recently found Jump Point Search and it seems like a really interesting algorithm. But I wonder about what its performance is like when your grid is of infinite size. When searching diagonally, is ...
0
votes
1answer
20 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, ...
0
votes
2answers
82 views

A* GetNearest() implementation

I'm trying to implement pathfinding in my platformer and I'm having trouble coming up with a way to find the nearest node to a world point. I tried this: ...
1
vote
1answer
32 views

An algorithm to make one object follow another on a 2D grid

I am using Greenfoot, but this can apply to pretty much any 2D engine. So my question is a basic one that I somehow couldn't find an answer to already. Basically, if I have an enemy and the player, ...
-1
votes
1answer
126 views

Sebastian Lague's A* star pathfinding “On condition”

As the title suggests I have been following the wonderful series of tutorials dealing with pathfinding made by Sebastian Lague. My problem is that the code is meant to be working immediately after ...
1
vote
0answers
26 views

Find the optimal position minimising the total path cost to multiple goals (A-star without a starting position?)

I have a 2D grid of discrete tiles, where some tiles (W) are impassable. Given a number of goals (G), what is the best way to find the position that minimises the total cost to all the goals? Example:...
3
votes
1answer
126 views

Dodge different type of obstacles

I'm writing a 2D game where the player has to kill a Ninja. This Ninja is coming closer with a constant speed chasing the player. The Map has some static obstacles like stones no one can pass. The ...
0
votes
2answers
48 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 ...
1
vote
1answer
39 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 ...
0
votes
0answers
26 views

What are pixel-based path finding algorithms? (path doesn't need to be shortest)

I have a canvas of size of approximately 1000x1000 pixels. I also have a matrix that represents that canvas and returns -1 if that 'pixel' is walk-able. I need to find a path between one of my objects ...
3
votes
0answers
33 views

How to implement path-finding with a large number of blocking agents following similar paths?

I want to implement a demo like creeps laning in Dota 2. So for simplicity, there is Left team and Right team, they are enemies. Units from Left team move toward Right base, and units from Right team ...
1
vote
1answer
52 views

How can I divide a grid map into clusters for path finding algorithm?

I am trying to implement HPA algorithm for finding the shortest path between two point. I came across the paper Near Optimal Path Finding Algorithm (by Botea, Müller & Schaeffer) but I am stuck at ...
1
vote
0answers
97 views

How to improve my RPG/RTS pathfinding AI?

Recently encountered this path finding problem while doing a RPG game. I am using Godot engine and pathing with A* and small cells. I also searched some other algorithm or technique like flowfield or ...
1
vote
1answer
65 views

Finding a path with minimal number of turns on a grid?

There is a path, generated by my implementation of A*, where diagonals aren't allowed, and the heuristics is the Manhattan distance. Is there a way to always or nearly always find a path with the ...
1
vote
1answer
62 views

Godot: How do I asign movement cost to tiles in a Tilemap?

Pathfinding I am trying to apply godot's Navigation to create a pahtfinding enemy in a Platformer game. I've read about a method to allow for pathfinding to take into account gravity. My issue is ...
1
vote
2answers
43 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
0answers
15 views

How to modify A* so that it takes into account the number of movement point left?

Context : turn based game, grid system Let this graph here : (A)-2-(B)-1-(C) | /| / 1 2 2 1 | / |/ (D)-1-(E) My unit is at A and wants to go at C. ...
0
votes
0answers
27 views

Unity Waypoint system

I am trying to code a way to choose between multiple paths using the waypoint system. I tried it with if statements but it was just very inefficient. Can anyone suggest me some ways to get this done? ...
0
votes
2answers
143 views

How to generate a random path on a 2d Grid

I want to create a random path in a 2d grid given a start point at the bottom row and an end point at the top of the row. I do not want the shortest path, or even the longest. Instead, I want a random ...
1
vote
1answer
99 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
1answer
93 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
1answer
94 views

A* heuristic for use with Goal Oriented Action Planner

Many of the high-level descriptions I've found for GOAP and similar planners suggest using A* for their path-finding, but I'm struggling to implement it for my own planner. Specifically, I'm ...
0
votes
0answers
35 views

How to do pathfinding with rectangular agents

I am making a wargame like the old Warhammer fantasy battles or kings of war. These games focus on the movement of large rectangular units on a continuous map rather than a grid. Units can only move ...
0
votes
0answers
16 views

Simple Automation of Car Path Finding Between 2 Points [duplicate]

I would think that it would be simple to have a car drive from A to B, but apparently I haven't been able to figure it out. My goal is to have a car begin at a certain position and angle, calculate ...
1
vote
1answer
40 views

Is there a way to automatically group tiles in a A* pathfinding grid to find the largest areas?

I'm making an RTS game using html canvas. I've made a program that randomly generates levels in order to test my pathfinding script. it divides the pathable blocks into squares so that you can apply A*...
1
vote
0answers
66 views

Is there an established way to create a 2D XY NavMesh in Unity?

Specifically, one in the empty space between colliders, rather than on an XZ plane (more or less) over the surface of a collider? Specifically this is because I have a drone, in a current project, ...
1
vote
1answer
94 views

A* Pathfinding Finding One of Many Goals

I have my A* pathfinding algorithm right now working such that given a graph it can find the route from one starting node to one goal node. This works well for many problems, but sometimes I find ...
0
votes
0answers
78 views

how to make AI do jump on navigation mesh system?

hi :D i'm currently using unreal for make a sand-box game for learning purpose. and due to the unique attribute of sand-box game, i am looking for how AI move naturally on map (which changes so often)...
1
vote
2answers
95 views

Recursively calculate possible pathway on a grid depending on max walk distance

I have a character that is placed on a grid. It has a variable maximum walking distance. Grid fields can be walkable or not walkable. As the character may has to walk around certain not walkable ...
1
vote
1answer
54 views

Snake AI - Is a Hamiltonian approach valid for all grid sizes?

So, as has been done many times before, I am designing an AI that can play Snake as effectively as possible. It didn't take me long to find this extremely useful thread here: How to find a safe path ...
15
votes
4answers
6k views

A* Algorithm for Tactical RPGs?

I'm messing around with writing a really poor tactical RPG in C++. So far I have a 2D tile map and just got the A* algorithm working based on the pseudocode in the wikipedia. But real tactical RPGs ...
2
votes
1answer
96 views

Closest node in A* pathfinding

For my 2D Unity game, I've implemented A* pathfinding based on waypoints. System already handles building graph from waypoints on scene (which are manually placed objects), as well as finding and ...
0
votes
1answer
82 views

A* Quad/Oc Tree path-finding vs Navigation Mesh path-finding

Main What are the differences between those path-finding algorithms. Is Navigation Mesh faster in finding the path? Is it more correct than Quad/Oc Tree? Does Navigation Mesh use Quad/Oc tree under ...
4
votes
2answers
113 views

Pathfinding with non-deterministic transitions between nodes

Consider a map not unlike a board game, where some of the moves are made non-deterministic. For example, moving onto certain cells will require you to roll a dice to determine where you should move ...
0
votes
0answers
13 views

Pathfinding/Steering with limited rotation [duplicate]

I am looking for an algorithm to guide some ships in a turn based game. The trouble is they should have a limited rate of turn, and I want them to navigate them to both a target position and a target ...
0
votes
3answers
77 views

Can I speed up “potential fields” pathfinding when it's working on a large grid?

I'm looking to implement a pathfinding algorithm that will allow me to throw hundreds of spiders at the players in my grid-based game. I can implement this with A*, but I'm worried that that algorithm ...
4
votes
3answers
161 views

RTS Unit AI: When to let the unit stop (due to local avoidence)

I am developing an RTS-like game, that have units that move and attack. I implemented path-finding and local-avoidance. One problem is when multiple units being ordered to the exact same position, ...
0
votes
2answers
88 views

Pathfinding How to store data for big terrain size

I am trying to implement my own pathfinding solution in unity but cant figures out how to store data. Following is my grid class which stores height, length and neighbour tile of tile. ...
0
votes
1answer
36 views

Shortest path to a road

I have a road network and a vehicle that is current off the roads. I want to find the shortest path to any road. An obvious solution is to run a pathfinding algorithm between the current vehicle ...
0
votes
2answers
528 views

Unity NavMesh pathfinding using Job System

I'm trying to write a system where I can run each enemy's NavMesh pathfinding in parallel, using Job System. The problem I'm having is that I can't pass the NavMesh agent argument as it's a reference ...
1
vote
1answer
81 views

Pathfinding to Get In Attack Range with “Transparent” Tiles

Currently I'm using A* and a raycasting algorithm to determine the path an entity (Player) should take to get close enough to the enemy (Enemy). The player has an attack range (it's illustrated around ...
1
vote
1answer
127 views

Correct way of combining A* and funnel

I implemented a pathfinding algorithm like this: There is a mesh of triangles that defines the area the player can walk. An A* algorithm is used for finding a path from the start triangle to the end ...
5
votes
1answer
206 views

Pathfinding in Procedural cave generation

I'm learning THIS tutorial about procedural cave generation using cellular automata with Unity. I want to implement pathfinding on some enemies, so I need to make a quantization of the procedurally ...
1
vote
1answer
98 views

Enemies overlapping

I have a simple WebGL maze game and has problem with enemies overlapping when they are going to target position. Now i'm detecting there collisions, but dont know what to do with them when they are ...
1
vote
2answers
125 views

Performance in pathfinding/road calculation

I have a question about the most effective way to detect road connection in a tile based world. Some time ago I already asked for "How to improve performance for expensive functions in 2d city builder"...
0
votes
3answers
118 views

Chunked A* Pathfinding Issues

I've run into an issue with A* pathfinding in a chunked world. This is my current setup: The world is designed in Tiled and exported as a .json file. I wrote a little program that converts the .json ...
0
votes
1answer
134 views

Generating nav meshes from tile based map (2D)

I'm working on a pathfinder for a MMORPG game, it's not mine; I'm RE it, now I need to create a pathfinder for monsters. But I figured that the client uses tiles for it's pathfinder (for players). ...
2
votes
1answer
28 views

Get the XZ to the right of a rotated point?

I need to do this entirely with math, take a look at this picture: What I'm doing is building a path finder algorithm that basically looks 30 units ahead, raycasts a few times perpendicular to the ...
1
vote
1answer
100 views

Looking for a square-to-hex pixel coords algorithm

So as the headline suggests, I am looking for an algorithm/algorithms used for square-to-hex and hex-to-square pixel coordinates convertion. I have an image which looks kinda "interpolated", meaning ...
3
votes
2answers
418 views

How can I maneuver an AI pirate ship for a sea battle?

I'm trying to picture in my head what would be required to make an AI controlled enemy do the following in a top down pirate sailing game: Approach the player ship Bring player in line with port / ...