Software Engineering Stack Exchange
Software Engineering Stack Exchange

Questions tagged [path-finding]

15 questions
41
votes
4 answers

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 order in which they were pressed, which obviously…
Raed Tabani
  • 537
  • 1
  • 4
  • 7
6
votes
1 answer

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, diagonal). For each of the nodes of Type 1, I want to…
Qqwy
  • 4,709
  • 4
  • 31
  • 45
6
votes
1 answer

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 approach that calculates both the euclidian…
Synesso
  • 574
  • 4
  • 11
3
votes
3 answers

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 state, so I need to find a path to walk from the…
Unknown Coder
  • 141
  • 5
3
votes
1 answer

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 do now is increase the path that it can make…
Macross
  • 41
  • 4
2
votes
1 answer

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. Quick draw of how it's organised: Superclass…
JC97
  • 131
  • 4
2
votes
1 answer

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, I don't even see why it works on the following…
edouard.gilles
  • 23
  • 3
1
vote
1 answer

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 struct edge { int nodes[2]; float cost; //…
a a
  • 261
  • 1
  • 7
1
vote
2 answers

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 the number he diced. The user should not be allowed…
Lolo
  • 11
  • 1
1
vote
1 answer

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 bit. I have a map with an arbitrary number of…
Cylindric
  • 119
  • 2
1
vote
1 answer

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 directions that are not obstructed by an…
Greg Gacura
  • 38
  • 3
1
vote
2 answers

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 I can enter the tile in front of me, which is…
user219317
  • 13
  • 5
0
votes
2 answers

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 this (maybe not the best example): I want to…
DrDress
  • 127
  • 4
0
votes
1 answer

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 find the best path from a to b. The next step would…
Andreas
  • 299
  • 1
  • 8
0
votes
2 answers

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" tile is on the grid. How could I best find the…
Jeff smith
  • 341
  • 3
  • 7