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]

The tag has no usage guidance.

-2
votes
1answer
58 views

Waypoint generating algorithm for graph [on hold]

I've got a graph filled with 'walkable' nodes that I want to generate waypoints for. I've searched for some articles on this but have come up empty-handed. There's over 2 million tiles (walkable nodes)...
0
votes
1answer
75 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 ...
0
votes
2answers
202 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 "non-walkable" ...
1
vote
2answers
257 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 ...
1
vote
1answer
314 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 ...
5
votes
1answer
113 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, ...
1
vote
1answer
133 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 ...
2
votes
1answer
246 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. ...
27
votes
3answers
15k 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 ...
6
votes
1answer
336 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 ...
2
votes
1answer
1k 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
2answers
884 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 ...
2
votes
1answer
678 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 ...