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.
253 questions
1
vote
0
answers
52
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 \...
- 31.8k
4
votes
2
answers
118
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)\$...
- 31.8k
0
votes
0
answers
52
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\$ ...
- 31.8k
4
votes
1
answer
275
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\$ ...
- 31.8k
1
vote
0
answers
59
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 ...
- 31.8k
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 ...
- 31.8k
4
votes
1
answer
124
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
...
- 31.8k
1
vote
0
answers
68
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
...
- 31.8k
1
vote
0
answers
32
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
...
- 31.8k
3
votes
1
answer
77
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
748
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
140
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
227
views
4
votes
1
answer
675
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