Questions tagged [path-finding]
The path-finding tag has no summary.
15 questions
1
vote
1
answer
459
views
What is the best way to program a lattice graph?
What is the best way to program a graph like this:
I know I could use Adjacency list or Adjacency matrix:
//https://stackoverflow.com/questions/5493474/graph-implementation-c
//Clearer's answer
...
- 261
3
votes
3
answers
797
views
What algorithm should I use for this game problem?
I have a grid-based puzzle game, that is based on states. I need an algorithm that can find a solution for each game level. A game level starts in a specific state and ends in a unique, well-known ...
- 141
0
votes
2
answers
243
views
Drawing all lines from right to left - fast
I have several drawings from SVG files which basically contain basic outlines of figures. They are constructed in segments of various shapes (lines, ellipse arcs, Bezier curves ect.) Something like ...
- 127
0
votes
1
answer
174
views
Find nth best path in graph G from node A to node B (without loops)
I'm making an graph layout optimizer and need to find paths from node a to node b in graph g. It has gone pretty well so far, but I lack an algorithm to take the next step.
So far I've used BFS to ...
- 317
0
votes
2
answers
303
views
How to represent shortcut nodes in Java?
How would I implement a shortcut finder into an A* path-finding algorithm? Assume that every tile is represented by an (x,y) coordinate, and I know where every "good" tile and every "...
- 341
1
vote
2
answers
862
views
How to find all possible paths with specific length in hexagonal game board?
I am currently developing a simple game in Unity.
I got a game board composed of hexagons. Let's say, the red dot is the player.
Now I want to show the user on which fields he can go, depending on ...
- 11
1
vote
1
answer
753
views
Help with algorithm to find optimal route between various routes, where order matters
This seems to be a variation on the Travelling Salesman problem, and I started (as
far as some reading at least) going down that route to solve it, but the ordering restrictions are confusing me a ...
- 119
6
votes
1
answer
149
views
What is the fastest algorithm to find what point of Type 1 is closest for each point of Type 2 on a rectangular grid?
In my contrived example, I have a rectangular grid of nodes, where each node is either empty, of Type 1 or of Type 2. All nodes are directed to the eight nodes around them (horizontal, vertical, ...
- 4,937
1
vote
1
answer
320
views
Pathfinding and Exploration
Here is my use case:
I have a two dimensional grid and each grid space is either open or blocked. I know the entire grid beforehand and as I traverse the grid I explore in a radius of 10 units in all ...
- 38
2
votes
1
answer
580
views
Algorithm to check for legal moves in Cluedo boardgame
I'm making a Clue(do) board game in Java to improve my programming skills. I've done a lot of work so far, but now I'm stuck at finding an algorithm to make sure if a player can make a certain move.
...
- 131
44
votes
4
answers
54k
views
What algorithm is used by elevators to find the shortest path to travel floor orders?
I'm trying to simulate an elevator, as always I started very simple by taking only a single order at a time, then added memory to the elevator in the form of queues so that floors are traveled in the ...
- 567
6
votes
1
answer
2k
views
Mixing heuristic functions in A*
I have applied a custom heuristic to my A* search. It is admissible, but it is not consistent (monotonic). As such, I am not guaranteed to find the shortest path.
I had assumed I could use a hybrid ...
- 574
2
votes
1
answer
2k
views
Yen's k shortest paths algorithm
I'm currently trying to understand Yen's k shortest paths algorithm. I based myself on the original paper as well as on the Wikipedia article, but still cannot see why it is correct if k > 2. In fact, ...
1
vote
2
answers
2k
views
Algorithm for finding all empty tiles in rectangular grid?
I have a rectangular grid of square tiles, some of which are blocked/filled. I start at a random tile inside the grid with the blocked tiles, randomly placed. I can turn in 90° steps and check whether ...
- 13
3
votes
1
answer
2k
views
A* with possible multiple paths
I am currently studying pathfinding and I came across A* algorithm from this site https://github.com/qiao/PathFinding.js
I tried to test A* with bi-directional and it is working great.
What I wanna ...
- 41