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.
254 questions
1
vote
1
answer
99
views
Jump point search in Java for faster pathfinding in grid mazes
(Refer to the entire repository in GitHub.)
How it looks like
Intro
This time, I present my take on Jump point search that I translated from Javascript (PathFinding.js/src/finders/JumpPointFinderBase....
- 32.1k
4
votes
1
answer
89
views
Dijkstra's algorithm for non-uniform undirected hypergraphs: Take II - bidirectional Dijkstra's algorithm with excellent performance
Intro
(See the full repository here.)
A non-uniform undirected hypergraph is a generalization of an undirected graph. It is defined as \$H = (X, E)\$, where \$X\$ is the set of vertices and \$E \...
- 32.1k
4
votes
2
answers
140
views
Dijkstra's algorithm for non-uniform undirected hypergraphs
Intro
(Repo here.)
A non-uniform undirected hypergraph is a generalization of an undirected graph. It is defined as \$H = (X, E)\$, where \$X\$ is the set of vertices and \$E \subseteq \mathcal{P}(X)\$...
- 32.1k
0
votes
0
answers
59
views
Computing \$k\$ most reliable paths in undirected probabilistic graphs in Java
Intro
(See MostProbablePath.java.)
This time, I elaborate on Computing most probable (reliable) path in a probabilistic graph (take II): instead of computing the most reliable path I now return \$k\$ ...
- 32.1k
4
votes
1
answer
285
views
Computing most probable (reliable) path in a probabilistic graph (take II)
Intro
A probabilistic graph \$G = (V, E)\$ is an undirected graph with weight function \$w \colon E \rightarrow [0, 1]\$. In the most reliable path problem we -- given two terminal nodes \$s \in V\$ ...
- 32.1k
1
vote
0
answers
64
views
PathFinding.java: Drawing a random perfect maze via randomized DFS
Intro
Still working on PathFinding.java. This time I concentrate on three private methods of GridModel that are responsible for generating random perfect mazes. A maze is perfect if for each two cells ...
- 32.1k
0
votes
0
answers
23
views
PathFinding.java: SettingsPane class
Intro
I am still working on PathFinding.java. This time I need to get reviewed the class responsible for choosing the heuristic function, the finder implementation, just to mention a few of settings ...
- 32.1k
4
votes
1
answer
136
views
PathFinding.java: Beam search in Java
Intro
I am currently working on this project (PathFinding.java). This time, I need to get the following class reviewed:
Code
...
- 32.1k
1
vote
0
answers
71
views
Fixed BIDDFS (bidirectional iterative deepening depth first search) in Java
Intro
I have this GitHub repository for doing pathfinding in directed unweighted graphs. This post is about BIDDFS proposed by Richard Korf in his paper.
Code
...
- 32.1k
1
vote
0
answers
40
views
LibID: a Java library containing some iterative deepening algorithms for pathfinding on directed unweighted graphs
Intro
I have this GitHub repository containing some iterative deepening pathfinding algorithms.
Code
...
- 32.1k
3
votes
1
answer
86
views
More shortest unrestricted paths to touch every square in an n by n grid
This is a part two.
The problem originates from here,
it is solved for \$n<11\$. A GitHub repository for this code, printing paths, and a collection of all proven best paths, it is open to ...
- 203
7
votes
1
answer
756
views
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 ...
- 203
5
votes
5
answers
1k
views
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.8k
3
votes
1
answer
146
views
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 ...
0
votes
1
answer
238
views
4
votes
1
answer
700
views
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
6
votes
2
answers
353
views
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
6
votes
2
answers
2k
views
5
votes
2
answers
1k
views
1
vote
0
answers
190
views
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?
...
- 19
1
vote
2
answers
241
views
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
2
votes
2
answers
453
views
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
5
votes
0
answers
210
views
Dijkstra's algorithm in Perl
I have this Perl module project.
My implementation of the Dijkstra's algorithm follows:
...
- 32.1k
6
votes
3
answers
551
views
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 ...
- 264
3
votes
1
answer
209
views
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 ...
- 32.1k
2
votes
1
answer
125
views
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
4
votes
1
answer
395
views
Searching for a performance bug in a C++20 pathfinding algorithm (NBA*) - follow up
I have followed some advice in the previous iteration, yet even the current version is too slow compared to the Java implementation of the same algorithm. (C++ version with ...
- 32.1k
4
votes
1
answer
202
views
Searching for a performance bug in a C++20 pathfinding algorithm (NBA*)
(See the next iteration.)
I have this pathfinding algorithm:
DirectedGraph.hpp
...
- 32.1k
1
vote
1
answer
132
views
Pathfinders.hpp - Dijkstra's algorithm
I have this Visual Studio 2022 project, in which I compared the performance of 4 point-to-point shortest path algorithms. This one presents the Dijkstra's algorithm:
...
- 32.1k
2
votes
2
answers
498
views
4
votes
3
answers
463
views
Improving generic A* algorithm performance
Here is my A* algorithm. I tried hard to implement it generically, but come up only with one idea to use lambdas for heuristic and next nodes (neighbours / successors) functions. I know that using ...
- 51
2
votes
1
answer
134
views
Shortest route algo terribly slow
First post. I posted this on stack as well but somebody suggested I post it here too/instead.
I wrote a shortest-path script for a Unity game project, and while it works, it gets so slow when applied ...
- 21
5
votes
3
answers
662
views
Compute shortest path in undirected graph
In a recent coding interview I was asked to write a program which takes as input two text lines:
The first one represents a graph, formatted as a sequence of undirected edges like ...
- 51
1
vote
1
answer
389
views
Google Foobar challenge optimization
I am trying to solve Google Foobar challenge prepare-the-bunnies-escape using my own approach, instead of BFS. I attempt to solve two ends of the maze and try to ...
- 146
2
votes
0
answers
124
views
AStar Implementation and Efficiency
This is my implementation of an AStar-like algorithm for maze solving.
A quick summary of the problem I am trying to solve with my algorithm might be:
A simple binary maze is given to you to solve, ...
- 121
2
votes
0
answers
77
views
Dijkstra from scratch
I implemented the Dijkstra algorithm from scrath and wonder if I can save some code? The whole algorithm is here.
n is the number of nodes, and m the number of edges. 1 ≤ 𝑛 ≤ 10^4, 0 ≤ 𝑚 ≤ 10^5, 𝑢 ...
- 355
3
votes
1
answer
849
views
How can I speed up my IDA* algorithm for N-puzzle?
I'm trying to solve the N-Puzzle problem using IDA* algorithm with a Manhattan heuristic. I already implemented the algorithm from the pseudocode in this Wikipedia page (link).
Here's my code so far :
...
- 191
5
votes
1
answer
535
views
A* Pathfinding Algorithm
I have programmed a A* Pathfinding algorithm in the Console. I would now like to know if there are any things that I could do to improve the time it takes, to find a path. Right now it takes around ...
- 59
8
votes
3
answers
2k
views
A* (shortest path) with the ability to remove up to one wall
Problem
You are given an HxW matrix. Each element is either 0 (passable space) or 1 (wall).
Given that you can remove one wall, find the shortest path from [0,0] (start)
to [width-1, height-1] (end).
...
- 183
4
votes
1
answer
92
views
Navigating the robot by finding the shortest way
I have this task where I have to make my robot find the shortest way when I enter a destination point. I've created some functions to assign numbers (distances) for each square and counts its way back ...
- 49
10
votes
2
answers
4k
views
Implementation of Dijkstra's algorithm in Python
I have implemented Dijkstra's algorithm for my research on an Economic model, using Python.
In my research I am investigating two functions and the differences ...
- 103
6
votes
1
answer
1k
views
Python: Astar algorithm implementation
I have implemented Astar algorithm for a problem on an online judge relating to maze given start and end positions along with a grid representing the maze. I output the length of the path along with ...
- 555
5
votes
1
answer
208
views
A* and ALT pathfinding in C tips
I adding some pathfinding to a game I'm working on. It primarily used A* with as suggested in the pathfinding articles at reb blob games.
It works, but isn't very fast.
It is a square grid map that (...
- 161
7
votes
2
answers
815
views
C#: A* pathfinding - performance and simplicity
Yet another implementation of A* pathfinding. It is focused on:
Performance (both speed and memory allocations).
Readability and simplicity.
Well defined objects and methods.
Accordance with general ...
- 390
4
votes
2
answers
359
views
Speed Up Flow Field Algorithm?
I am slowly creating a flow field pathfinding solution for Unity3D. I'm trying to follow Elijah Emerson's description, which appears in the book 'Game AI Pro' (volume 1). In this question I ask about ...
3
votes
1
answer
126
views
Coordinates Struct for Flow Field Pathfinding... am I doing this right?
I am slowly creating a flow field pathfinding solution for Unity3D. I'm trying to follow Elijah Emerson's description, which appears in the book 'Game AI Pro' (volume 1).
The map is divided into ...
4
votes
2
answers
657
views
I wrote my first pathfinding algorithm
I'm currently writing a small game in Lua, using the Love2d framework. I guess I'm doing it as a practice of sorts, but it did give me the opportunity to write my first pathfinding algorithm. I wrote ...
- 41
2
votes
1
answer
388
views
Sum of all Paths in Binary Tree
Problem
For the given binary tree return the list which has sum of every paths in a tree. i.e Every path from root to leaf.
I've written following solution.
...
- 281
1
vote
0
answers
389
views
Directed graph and Dijkstra algorithm using heap
I have implemented directed graph and Dijkstra algorithm using heap in Python.
I first implemented an abstract base class WeightedGraph, of which ...
- 256
5
votes
2
answers
121
views
Performance Enhancement of A Star Path Finder algorithm with 1024 multidimentional array
I have the below code for a A* pathfinder, however it is taking upwards of 10 minutes to find a solution using a simple 1024 x 1024 array.
I had to comment out ...
- 51