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.
243 questions
7votes
1answer
707views
Shortest unrestricted path to touch every square in an n by n grid
The goal is to brute force the length of the shortest unrestricted path that touches any part of each square within an n by n square grid. Unrestricted path meaning any continuous curve between two ...
- 71
4votes
5answers
991views
Faux Random Maze Generator
For a personal project, I've written a maze generator in Python that I will be using A* to navigate through (using C++). The biggest points of improvements I'm looking for are in the generation itself....
- 10.7k
3votes
1answer
122views
Multithreaded 8x8 grid 63-move path Pathfinding
This program primary effort is the pathfinding of an 8x8 grid without the use of Java Collection Framework. The starting cell is at the top left corner and the end is the bottom left corner. All valid ...
0votes
1answer
221views
4votes
1answer
629views
Multithreading a shortest path algorithm
I would like to modify my shortest path finding code to use multithreading and improve its performance. The algorithm must be able to work with negative weights, and as a result, we cannot use ...
- 263
6votes
2answers
319views
Bellman-Ford optimisation in C with Shortest Path Algorithm (SPFA) and Small Label first (SLF)
I am trying to code an optimized version of Bellman-Ford algorithm. This post is a continuation of the following post Bellman-Ford optimisation in C in which I posted a first version of the classic ...
- 263
6votes
2answers
2kviews
5votes
2answers
995views
0votes
0answers
165views
A-star pathfinding algorithm to route through a raster maze
I have a problem that needs path finding to solve. It is a vector of ints; 1 for passable terrain and 0 for non-passable. My implementation is not fast enough for the test. How could I make it faster? ...
1vote
2answers
209views
Finding the cheapest path between two points using Dijkstra
I am trying to use Dijkstra to find the cheapest path between two pixels in an image. Implementation: ...
- 185
2votes
2answers
412views
Optimizing a recursive path finding algorithm
On input i get width and height of matrix, string of text and another string of finalText I want to reach. The characters of the first string are assigned to matrix. My goal is to find shortest way to ...
- 21
5votes
0answers
189views
Dijkstra's algorithm in Perl
I have this Perl module project. My implementation of the Dijkstra's algorithm follows: ...
- 30.2k
6votes
3answers
508views
The shortest path between airports
Airlines need to provide their customers with flights to every corner, so they need an app that allows them to do so. The customer must be able to transfer when there is no direct connection. The ...
3votes
1answer
169views
Traditional vs. bidirectional Dijkstra's algorithm in C
I have this CLion project on GitHub. It constructs a directed, weighted graph consisting of 100 thousand nodes and 500 thousand directed arcs, picks two random nodes, and computes the shortest paths ...
- 30.2k
2votes
1answer
110views
Priority Queue for D* Lite
So, I needed a priority queue for D* lite and I wanted to know whether this is an acceptable implementation or not. ...
- 157
