Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.
1
vote
1answer
28 views
Path finding: avoid being surrounded by enemies
I'm building a bot that plays a simplified version of Pac-Man. The bot does a pretty good job, but sometimes it chooses a path where it ends up surrounded by enemies.
Here is an example:
...
4
votes
2answers
64 views
Pathfinding in Isometric Phaser with Tunnels
I want to create a 2D isometric game. Currently I'm looking and testing Phaser game engine with isometric plugin. Almost everything at the moment looks possible except few things. I will create a ...
1
vote
4answers
106 views
How can I “smoothen” my path-finding on a map with big tiles?
I've just implemented A* in my "game", but as I finished it this came to my mind:
This is fine for a turn based game, but it would be really annoying for a real-time one.
For example look at the ...
3
votes
1answer
98 views
Tile Based A* Pathfinding, but with a bomb
I've written a simple A* path finding algorithm to quickly find a way through a tile based dungeon in which the tiles contain the information of walls.
An example of a dungeon (only 1 path for ...
1
vote
1answer
40 views
Pathfinding with multiple actors moving in sync
I am trying to implement a path-finding routine involving the following:
Multiple agents
Multiple Goals
Obstacles
Both agents move in sync, i.e. they both move in the same direction unless one is ...
0
votes
1answer
133 views
A* algorithm works silly with heap
I'm trying to use A* and visualised it, but when i add a heap optimization it start looking in incredeble ways sometimes normal(better then next to be sure), somtimes he looks on few columns.
Normal ...
1
vote
2answers
83 views
HPA* Pathfinding, building the hierarchical graph is too slow
So I have a graph, roughly grid shaped, that is about 300*300 nodes large. Even at this size, however, traditional a star takes 20 seconds to run in some cases. So I implemented an HPA* algorithm to ...
0
votes
2answers
83 views
Why is my A* algorithm slow?
I made an A* algorithm, but running it is unbearably slow, even on a 40 x 40 test arena with few obstacles. I've tried changing the unexplored array to exclude nodes in the open list, and although it ...
8
votes
3answers
156 views
Can A* path finding cost functions allow for path following shapes?
Recently I begun developing a game prototype which could create procedural generated dungeons using a collection of room types. To ensure the hallway paths between these rooms would always be ...
0
votes
1answer
47 views
Is A* suitable for this particular case?
I have a 2D map of nodes a train could travel. They are not in a grid. The node positions are placed by a designer and exported to a JSON file which the game loads to display the node positions on the ...
1
vote
0answers
25 views
Agent avoidance in 3D
I am currently trying to find some alogorithm for agent avoidance in 3D (or for simplicity, 2.5D could be enough).
So far, I have been using variation of RVO - "Reciprocal Collision Avoidance" (C++ ...
0
votes
2answers
59 views
Make Enemies Walk Next to the Player
I know the A* algorithm but if I have a long range (firing) enemy 20 metres away in 2D-land and I want it be about 3 metres away from its target (aka the player).
Is there an algorithm for choosing ...
1
vote
1answer
67 views
Unity Navigation & Pathfinding and A star algorithm
I just tried to follow a tough tutorial about A* path finding in Unity C#. I have also tried Unity own Navigation & Pathfinding system which is actually quite easy to understand and implement. I ...
4
votes
1answer
120 views
How to find the nearest object from another, in a non tile based game where obstacles are present?
The nearest object means the path from the initial position to this object is shorter than the path from initial position to any other object. The path is the smallest number of pixels this object ...
0
votes
2answers
67 views
A* movement implementation not working properly
I'm working on a RTS project and I'd like to use the A* Project by Aron Granberg to navigate around obstacles, etc.
The problem is that the correct path is displayed in the scene, but the unit just ...
4
votes
0answers
84 views
Path finding. How to find a safe path for an AI snake?
I have been working on this project on and off! The project involves a game in which a player can compete with a snake ai to get the most apples. The current path finding technique i use (A* ...
5
votes
1answer
110 views
Finding N shortest paths
I know about several of path-finding algorithms that exist: depth-first search, Dijkstra's algorithm, A* etc.
Now I would like an algorithm that gives me the N paths with lowest cost. Can this be ...
0
votes
0answers
34 views
Find required entities to accomplish specific task in shortest time
I have a grid like map with entities that can perform turn-based actions like moving or growing strength. When I have a task that requires a certain strength, I want to find the entities required to ...
1
vote
1answer
117 views
Voxel river flow simulation
I am making a Voxel game and I'd like to add rivers that can be redirected. So I thought that if a player replaces a river block or digs up a block next to a river block the river would repath itself ...
4
votes
2answers
125 views
Pathfinding in non-quantized space?
Pretty much whenever anyone thinks about pathfinding, they think about algorithms like A* and DFS - graph search algorithms, which also just so happen to work as pathfinding algorithms when you ...
2
votes
2answers
119 views
Strategies for using Dijkstra's Algorithm on “larger” (4096+ node) graphs (tower defense)
I am using Dijkstra's for pathfinding in my 2d game, my game is similiar in style to a tower defense game which has waves of monsters trying to reach a goal. I am currently building the paths while ...
0
votes
1answer
72 views
Pathfinding: grid based map of irregular numbered tiles to mark connections
Given this map:
The floor tiles are separated from the rest (its a map made in Tiled in separate layers) and as you can see, the id numbers are not in sequence.
¿How I would go about making ...
1
vote
0answers
41 views
How to convert an octree to a 3D array
I have an octree that I'm planning to use for 3D pathfinding. My plan was to break down the world such that all the leaf nodes of the tree would be of equal dimensions that would create a nice grid ...
4
votes
2answers
71 views
Make a cell's content 'listens' to another cell (the closest cells)
I'm a newbie in programming and in java and I need some lights and help.I'm developing a game in which two players have to play with tokens (say red and blue) by placing them in cells (75x75 grid). ...
0
votes
0answers
41 views
Basic Theta Star Pathfinding Implementation Question
My goal is to implement any angle pathfinding in a 2D sprite based game. The levels are based on 2d square grids with a top down perspective (retro RPG theme), although units can move freely at any ...
0
votes
0answers
78 views
What is the best way to generate a non-grid, rail-like path from prebuilt pieces?
I'm trying to procedurally generate a path from prebuilt pieces, like one would from a train set (straight piece, 45° turn, 90° turn, etc.). Generating the path randomly is simple enough but I'm ...
0
votes
1answer
93 views
How to create a path-finder for a map like this?
I'm not sure if this is considered grid-based, because as you can see there is also a line. And that line is also a non-walkable point, I have no idea how do I create a path-finder with a non-grid-...
2
votes
2answers
32 views
Picking cells which form a completed line between to 2d grid cells
I'm using Bresenham's line algorithm to calculate a "line" of cells between a start and end point on a 2D tile grid.
However, I'm using this during terrain generation to create a visible pathway, ...
1
vote
0answers
238 views
Path finding algorithm for (x,y) coordinates in c++
I am trying to code a path finding function in c++ . It should work like that, you supply the start point (x1,y1) and the end point(x2,y2) and it returns a list of points for the shortest path.
...
2
votes
1answer
27 views
How does Hierarchical Pathfinding deal with obstructions in the same chunk?
Aigamedev.com provides this visualization of HPA*:
All the nodes within the same chunk connect to each other. What if there was an obstruction between nodes in the same chunk? For example:
What ...
0
votes
1answer
72 views
2d grid for 3D game
I have a 3D game dungeon crawler game. It's procedurally generated. I have a bunch of prefab rooms that are used to put together this dungeon. When not in combat the player uses a navmesh to move ...
1
vote
2answers
47 views
Board Game Pathfinding - Finding optimum valid path with limited path distance?
I'm building the very earliest stages of piece movement in a digital board game I'm planning to make.
It's a browser based javascript system.
Basically the players roll to move and need to traverse ...
5
votes
1answer
214 views
Reconciling Flocking and A* (Theory)
For my RTS game I have got A* pathfinding working, and that's fine. Basic collision detection exists too. When a unit is moving it checks if the position it will occupy next move is a node occupied ...
2
votes
2answers
67 views
Given a grid system where some coordinates are marked as impassable, how to find natural-looking car driving path between two locations?
I can compute an A* path, but I get only cardinal directions from that. A 45˚ path would look like "up 1 left 1 up 1 left 1 up 1 left 1..."
My specific question is, given a grid with a pathing ...
0
votes
1answer
123 views
How to make Djikstra algorithm remember path?
I understand how dijkstra algorithm works but I don't know how I should figure out path. How can I get nodes that are on the shortest path?
0
votes
1answer
177 views
How to implement a A star pathfinding in 3D world on Irrlicht
I am developing a little game. I need an A star path-finding algorithm for enemies who follow the player. I have already learned and tested a path-finding algorithm, but it works with fixed-size array....
3
votes
2answers
106 views
How to calculate area to fill in this Snake/Qix game variant?
I have a game which is a Snake/Qix variant.
The player controls a line which is moving on an island. Player has possibility to leave the island in order to connect that island to itself. Once the ...
2
votes
2answers
80 views
Grid Pathfinding with known points
What is the best way to, in a grid, to find a path (not necessarily shortest) from a start point to an end point (for both of which the coordinates are known)?
The grid is approximately 60x60, and ...
1
vote
2answers
147 views
when to do A* pathfinding?
I'm trying to build my first game, a really simple RTS like Age of Empires but I have a question about pathfinding.
When do this kind of games usually do pathfinding?
I've read some games do a ...
0
votes
1answer
276 views
JavaFX snake game AI
I am trying to add an AI simulated snake to my snake game that a player can play against. So far I think I do get the concept of how to do certain things but snake should be able to find the nearest ...
1
vote
1answer
98 views
Shared data in multithreaded pathfinding engine
Imagine a case where you have lots agents in a big world, who frequently need to calculate the shortest/best path from A to B. In this case it seems natural for me to create a pathfinding engine where ...
1
vote
1answer
296 views
NavMesh.CalculatePath returns invalid path Unity3D
I am trying to get coordinates for path from source to destination object using NavMesh. NavMesh.CalculatePath() is only working for one level surprisingly. For all others, it returns false. Also ...
2
votes
0answers
104 views
How to go about implementing pathfinding in Unity with Tiled2Unity map prefabs?
I have created a map using Tiled application and have added collision boxes and used Tiled2Unity to import the map to Unity. The collisions are working with key inputs.
I want to implement ...
-2
votes
1answer
195 views
Does A* actually find the shortest path?
It's said A* guarantees to find the shortest path but I think for certain paths with certain obstacles it won't find the nearest path. My example below is marked (with pink and blue lines) for what I ...
0
votes
1answer
76 views
How to get connect tiles in hexagonal Grid system
I've been developing a game where a number of tiles can drag into a hexagonal gird background.
But some purpose i need to find the location of same tiles into a array and marge them.
Data Layer
...
0
votes
0answers
68 views
View the path a AI is walking along in Unreal Engine 4
I'm using unreal engine 4.12.4 and I want to be able to see the path that an actor will use when i trigger "Simple Move To Location" and i want to see the path as a line in game for testing.
1
vote
0answers
117 views
How to implement A* pathfinding for enemies to follow player
The enemies in my game are supposed to follow the player in order to cause damage to it. Right now I have it where the enemy just goes in the direction that will bring it closer to the player, and ...
1
vote
0answers
125 views
UE4 Navmesh precision
I'm trying to make my very tiny man pathfind his way through a map of a school but the navmash won't recognize some of the hallways cause they are very narrow like this.
So as you can see the man ...
3
votes
1answer
76 views
Multilevel 2D grid graph and A*
I've coded up a little grid based dungeon game. Everything working quite nicely in a Tile[,]. The AI uses basic GOAP for tasks and A* for moving around. Tile reachability is done using a floodfill.
...
1
vote
1answer
100 views
What's an optimal procedure to create a connected cyclic grid of nodes and edges for A* pathfinding
like the title says, I'm trying to create a grid of nodes that hold edges or connections to each other so I can perform A* algorithm to have objects traverse across them as seen in your standard RTS.
...
