Stack Exchange Network

Stack Exchange network consists of 174 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
Make your voice heard. Take the 2019 Developer Survey now

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
1answer
31 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
32 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 ...
2
votes
2answers
84 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
10 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
62 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
102 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
69 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
30 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
1answer
179 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
64 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
votes
0answers
37 views

Astar Backtracking [duplicate]

I am using OpenCV to code an image based A* algorithm. Using the image, a grid of clear paths and obstacles are created, which the algorithm is run on. The red squares are obstacles, and the yellow ...
0
votes
1answer
99 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 ...
4
votes
1answer
177 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 ...
0
votes
0answers
48 views

Connecting nodes for pathfinding algorithm

I am attempting to build a program where a user is able to select a starting and ending point on a map, and the shortest path between those two points is displayed. My code should work for all maps ...
1
vote
1answer
71 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
86 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
99 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
59 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
27 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
95 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
371 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 / ...
2
votes
1answer
124 views

Pathfinding, 2+ tiles wide

I recently started learning python and I'm working on a dungeon generator, using images for the rooms, hallways and junctions. Example of desired result. So far I managed to generate a X * Y map and ...
0
votes
1answer
122 views

Can you use A* to make a unit move nonspecifically?

A* is typically used to calculate the best way to move towards something, and it's quite flexible when it comes to threats, extra movement costs, and 'refuelling' on the way to something. However, if ...
6
votes
2answers
499 views

RTS pathfinding

I'm doing my first RTS game (something like WarCraft 2) in own game engine using Monogame for graphics. I am wondering how can I implement pathfinding for a selected group of units. Movement is tile-...
0
votes
0answers
38 views

AStar Scores Explain Question. What is GScore?

I Tried to create AStar Algorithm and i'm already finished but i didnte work cause of this line : ...
0
votes
1answer
69 views

FixedUpdate is Being Called Less and Less Over Time…Why?

My game is still in the very early stages, but basically I have an enemy that follows the player if it can see them and will continue to follow the player for a few seconds after the player leaves its ...
1
vote
0answers
244 views

How can I achieve dynamic pathfinding in Godot?

I am new to Godot and trying to implement dynamic pathfinding on a 2D map which includes both static obstacles and moving units. As I understand it, Godot's NavMesh makes it almost trivial to generate ...
0
votes
0answers
312 views

Is Godot's NavMesh viable for dynamic pathfinding (e.g. avoiding moving enemies)?

I am a novice (read: low-budget) designer looking at moving from Pygame to a real engine, and between Unity and Godot it looks like the latter has a much better 2D engine [1, 2, 3]. I would be happy ...
1
vote
1answer
72 views

Potential Field Pathfinding in a non Axis Aligned World

I am trying to create a game that has player created obstacles which can be placed anywhere in free space, and which has a large amount of enemy agents. In persuit of maximizing the number of agents I ...
2
votes
1answer
593 views

How to make ghosts AI chase Pac-Man in Java

I'm beginner at Java and I want to make ghosts chase Pac-Man in game. I read some algorithm like A* or Dijkstra but I don't know how to implement them in my game. Please help me.
1
vote
0answers
109 views

Pathfinding towards a moving target in 2D Platformer

I have an enemy in my 2D platformer that chases the player around the level. I implemented a modified version of A* that works with gravity as described here: https://gamedevelopment.tutsplus.com/...
1
vote
2answers
71 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 ...
2
votes
1answer
99 views

How to implement the graph for pathfinding using A*

The game I am working on is based on a maze where each level is procedurally generated. The pathfinding grid is a 2D array where each node holds its connections. Path requests are handled one at a ...
3
votes
2answers
90 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 ...
2
votes
2answers
56 views

Determining connectedness of rectangles

I am working on some functions to use in my enemy state machines. I want to write a function which determines whether the platform the enemy is standing on is connected to the platform the player is ...
7
votes
2answers
518 views

Game AI move towards player while avoiding an obstacle

I'm trying to move enemy towards player, while enemy also tries to avoid an obstacle if it's in its path. Here's a simple illustration of what I want to do: What I've tried: Making circular ...
8
votes
1answer
170 views

A* implementation issue

I admit defeat, I must ask the community the same question it has been asked a million times before: "What is wrong with MY implementation of the A* algorithm?" I am getting some very wonky results, ...
4
votes
1answer
59 views

Navigate multiple Units on a grid through a tight space with different directions

I just started learning about pathfinding algorithms. Assume we have this scenario: Blue and Green can move only on those tiles. They can also talk to each other. Blue wants to go through the tunnel ...
2
votes
1answer
110 views

Path Planning in a chaotic, ever-changing environment

I've implemented Path Planning a few times, using A* on nav meshes, and also Continuum Crowds but now I am trying to plan paths in very chaotic environments. In this environment, new routes and new ...
0
votes
1answer
96 views

Can't figure out what's making the player teleport back to spawn

I've been working on a multiplayer game that uses pathfinding and I'm really confused over this one weird bug. On your screen, the other player glitches between the spawn point and his current ...
1
vote
3answers
488 views

How do you handle pathfinding for non-tilemap 2d games?

What methods do you use to handle path finding in non-tiled 2D games? Tilemap based methods can use A* and 3D has NavMesh available. The only success I’ve had is with raycasts but it doesn’t seem ...
0
votes
1answer
87 views

how to sync clients and local avoidance in mobile RTS game?

I have been making mobile RTS game in Unity look like Clash Royale similarly. Unfortunately, I faced to two big problems. First is two phones(clients) to be synchronized each other in game state. ...
1
vote
0answers
121 views

Game “Hocus”: How to do the path finding?

I rebuild popular apps to get good at Godot. This game Hocus poses a challenge in terms of path finding. I have a solution, but as the illusions scale, it becomes ridiculously time-consuming to set up....
3
votes
2answers
273 views

What is a good rule for blocking projectiles on a square grid?

Suppose we have a square grid, and each tile may or may not be occupied by an object. Some of those objects can be a unit that can launch a projectile at another unit. However, that projectile should ...
9
votes
3answers
2k views

How to reduce the time taken to path-find to an unreachable location? [duplicate]

I have a 2048x2048 map and if I path-find to an unreachable location, it makes the pathfinder go through every node on the map which freezes the thread for 4 seconds. How can I reduce that time? I'm ...
0
votes
0answers
95 views

How to compile RVO2 library for collision avoidance for RTS in Visual Studio 2017?

I have been banging my head for compiling RVO2 to my Visual Studio 2017 for a long time. Can anyone tell me how do i make it compile? Here is my Upgrade Log: For those who are unable to see, It ...
1
vote
1answer
319 views

Queueing with Unity's NavMeshAgent

I have created a strategy game where the units use Unity's NavAgent pathfinding and flocking algorithms. This works well. However, I need to add queueing so that units will queue sensibly. This ...
1
vote
0answers
140 views

2D Sideview Procedural Water Generation

How can I generate water in a procedural 2D sideview landscape? Here's what I currently have: First generate the heightmap of the land Then generate the water, based on the land Here's how I ...
1
vote
1answer
158 views

algorithm for Shooting objects that bounce off the wall

I'm trying to make a 2D game where my Hero is standing in a 2D plan and surrounded by enemies(highest 3) that throwing balls. and my hero have a shield in hands and and will stop the balls... well ...
0
votes
0answers
33 views

Optimise pathfinding failure - can I reduce the number of sweeps? [duplicate]

I've got pathfinding working on a simple 2D grid map. NPCs can now move around the board and avoid areas they cannot travel. This works well, and is carried out by a single sweep of the board to ...