Questions tagged [pathfinding]

Pathfinding or pathing is the plotting of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph.

Filter by
Sorted by
Tagged with
5
votes
1answer
4k views

BFS shortest path for Google Foobar “Prepare the Bunnies' Escape”

This is the Google Foobar puzzle "Prepare the Bunnies' Escape": You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is ...
2
votes
1answer
3k views

BFS shortest path for Google Foobar challenge “Prepare the Bunnies' Escape”

This is the Google Foobar challenge "Prepare the Bunnies' Escape": You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is ...
1
vote
1answer
839 views

NBA*: Very efficient bidirectional heuristic search algorithm in Java - follow-up

This post elaborates on NBA*: Very efficient bidirectional heuristic search algorithm in Java. I have made the following changes: Added an explicit type for representing digraph paths: ...
3
votes
1answer
174 views

F# implementation of the A* algorithm

This is my first attempt at writing something useful in F# and in a functional way in general. I would appreciate if you could point out any issue, even details, as I'd like to put all the bad habits ...
186
votes
4answers
30k views

Dijkstra path finding in C# is 15x slower than C++ version

I'm implementing Dijkstra's algorithm with a priority queue for a game I'm developing in Unity with C#. I was a bit disappointed with the performance, so I decided to port the code to C++ and see if ...
28
votes
4answers
75k views

A* search algorithm

NodeData stores all information of the node needed by the AStar algorithm. This information includes the value of ...
7
votes
1answer
1k views

Python program to find a word ladder transforming “four” to “five”

I saw this Puzzling problem and thought I would try to write a Python program to solve it. The task is to transform "four" to "five", forming a new four-letter word at each step, replacing one letter ...
5
votes
2answers
1k views

Fastest path on a snakes and ladders board

I am not looking for a detailed review of this code as I am aware it is very inefficient. The main reason for posting this is to see if there is a better way to achieve my goal (I am certain there ...
12
votes
1answer
620 views

Racetrack pathfinding and path following

Racetrack The August community challenge is to implement a program that plays the Racetrack game. Each player starts with an integer position on a square grid. On each turn, the current player can ...
5
votes
2answers
288 views

Codingame: Great Escape bot in Ruby

(EDIT: I incorporated a lot of the feedback from the answers, and posted a follow-up question here: Codingame: Great Escape bot in Ruby - Follow-up) I started working on some code challenges at ...
5
votes
1answer
3k views

A* Algorithm in C# for pathfinding 2D tile grid

I am very new programming and am trying to develop a small tycoon game as a hobby project in Unity. This algorithm executes beautifully but if 100+ agents are getting new paths simultaneously there is ...
5
votes
1answer
110 views

Shortest pathway across a snakes and ladders board (Update)

Earlier I posted a fairly inefficient recursive solution to the problem of getting across a snakes and ladders board in the smallest number of moves. I have created a much faster solution to this ...
3
votes
1answer
2k views

MazeRunner in Java

To test the queue I perfected from one of my CR questions, I've developed a maze program that receives an input maze, starting and end positions, and solves it. I have separate software that handles ...
3
votes
0answers
52 views

Fast algorithms in Javascript for shortest path queries in directed unweighted graphs

(There is a follow-up question available to this: Follow-Up Question) So I have this: ...
3
votes
1answer
170 views

Finding smallest number of moves

We are given a map of sides of length n and m (both n and m are less than 1000), divided into n*m fields (squares of side 1). The map looks (for example) like this: ...
2
votes
0answers
24 views

Fast algorithms in Javascript for shortest path queries in directed unweighted graphs - follow-up

(See the previous iteration.) Now I have reworked my pathfinder program, and I ended up with this: ...
1
vote
1answer
775 views

NBA*: Very efficient bidirectional heuristic search algorithm in Java

(See also the next iteration.) I have implemented NBA* (New Bidirectional A*) in Java and compared it against conventional A* and Dijkstra algorithms. The results may be as optimistic as this: Seed =...
0
votes
1answer
2k views

k-shortest path algorithm in Java

(See the next iteration.) This snippet is about computing \$k\$ shortest paths in a directed graph using this algorithm. I would like to hear about API design, naming/coding conventions, and so on. ...
4
votes
1answer
769 views

Dijkstra's shortest path algorithm in C

Now I have this C implementation of the famous algorithm: dijkstra.h: ...
3
votes
0answers
118 views

Codingame: Great Escape bot in Ruby - Follow-up

This is a follow-up to Codingame: Great Escape bot in Ruby. As mentioned there, my first reasonably sized Ruby project is a bot for CodinGame's Great Escape contest (here is a sample gameplay video). ...
3
votes
2answers
126 views

Computing most reliable path in undirected probabilistic graphs using Java

(See the next iteration.) Problem definition We are given an undirected graph \$G = (V, E)\$ and a weight function \$w \colon E \to (0, 1]\$. The weight of the edge \$e \in E\$, \$w(e)\$, ...
3
votes
1answer
2k views

Dijkstra's algorithm: traditional and bidirectional in Python

I have translated Dijkstra's algorithms (uni- and bidirectional variants) from Java to Python, eventually coming up with this: Dijkstra.py ...
2
votes
0answers
56 views

Faster k-shortest path algorithm in Java

In the \$k\$-shortest path problem, we are searching for (at most) \$k\$ distinct, shortest paths connecting two given terminal nodes. You can see the previous version here. This implementation, ...
2
votes
1answer
93 views

Computing most reliable path in undirected probabilistic graphs using Java - follow up

(See the previous iteration.) What I did Now I have took some (not all) good points from the previous iteration. Removed the entire weight function class, Got rid of node IDs, Improved the math a ...
1
vote
3answers
4k views

Dijkstra in C++ to find shortest path for every vertex of a directed graph

I am trying to implement the Dijkstra algorithm in C++ that finds the shortest path for a graph from a text file. The text file contains a matrix that represents a directed graph. What I am trying ...
1
vote
0answers
24 views

Wikipath stack in Java - Part II/IV - The implicit Wikipedia article graph

This question is the continuation of the Wikipath stack series: the two classes that - given a Wikipedia article \$A\$ - return the lists of neighbour articles. The forward node expander return the ...