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
0
votes
1answer
724 views

Node comparison using priority queue for Dijkstra's Shortest Path Algorithm

Instead of using a MinHeap that will allow me to change the vertex priorities I am using the Java library PriorityQueue. Here ...
2
votes
1answer
1k 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: ...
2
votes
1answer
1k 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 =...
7
votes
1answer
5k 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 ...
10
votes
2answers
1k views

2D grid Hamiltonian path puzzle solver

The puzzle goes like this: in a rectangular 2D grid there are empty spaces (.), exactly one starting point (S, ...
7
votes
3answers
8k views

Using a greedy algorithm to find the best path in a 2D array

I'm a student and this is one of my assignments. My professor basically confirmed that my code is correct but all he grades on is if I finished the assignment correctly but not the coding style. I ...
8
votes
1answer
8k views

Percolation Model

Newbie here, presenting the code for close public scrutiny. Couple remarks regarding the context (taken from Princeton's COS 226 course): In this problem I model a percolation system using an N-by-...
3
votes
1answer
311 views

Optimisation of A* in C++

I'm working on an A* pathfinding algorithm to solve a programming problem, and part of the constraint is the runtime. I need to find a path in a 2D grid with blocked or non-blocked tiles. You can't ...
1
vote
0answers
64 views

Thread pool based unweighted path finder in Java for graphs with slow expansion operator

Introduction Given a directed unweighted graph, the objective of this library is to find a shortest path from a given source node to a given target node. Clearly, one candidate algorithm to find ...
4
votes
1answer
208 views

A* Algorithm speed improvement

Currently I have a very general purpose A* algorithm, which I've submitted as open sourced at https://github.com/kd7uiy/AStar . I've been trying to speed it up for the last month or so, and while I'm ...
4
votes
1answer
636 views

Pathfinder from image file

I've created a simple pathfinder programme that receives its input from a very small .png file. Example file here: Here's a link to the file (note that the green pixel represents the start, the red ...
2
votes
0answers
2k views

Dijkstra's single source shortest path algorithm (with Fibonacci heap)

I implemented a generic Dijkstra algorithm. It's lazy since the vertices with their final distances are request on demand. I used the Fibonacci Heap from this question with a few changes (added a copy ...
4
votes
1answer
5k views

Weighted graph and pathfinding implementation in C#

I am implementing fundamental data structures in C#. I have written a weighted graph in Java so my main motivation here is to sharpen my skills in C#. I have tested with various cases and there seems ...
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 ...
11
votes
3answers
576 views

Dijkstra's algorithm in C99

I just implement Dijkstra's algorithm in C99. Can you review my code please? I'm looking for any mistake, performance improvement or coding style errors. main.c ...
3
votes
1answer
1k views

Matlab implementation of Needleman-Wunsch algorithm

This code (an implementation of the path finding Needleman-Wunsch algorithm), given two sequences, correctly aligns and calculates the similarity of them. For example, given two sequences: AAA,CCC ...
0
votes
1answer
551 views

Shortest path via two intermediate points

My code takes a long time for big graphs. How can I make it faster? I'm trying to calculate the shortest path for 3 path's using queue but for big input my program crashes. I'm stuck here. Can ...
4
votes
1answer
695 views

Dijkstra's algorithm

Assuming everything else works as expected, is the following a correct - but not the most efficient way - of implementing Dijkstra algorithm? Because I have tested it on several examples and it gives ...
4
votes
1answer
174 views

Algorithms to find various kinds of paths in graphs

I think many here are familiar with the graph data structure. Not very long ago, I implemented as an exercise a supposedly simple Graph application that does some traversals. To note, the most complex ...
2
votes
1answer
6k views

Shortest path in maze

Please help review my code. ...
3
votes
1answer
3k 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 ...
3
votes
1answer
257 views

MazeRunner in Java - follow-up

I've refined a lot of the code from my previous question, and have also decided to include the logic that interprets a given text file. Any advice on how to improve the actual algorithm that solves ...
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 ...
4
votes
1answer
2k views

Finding the longest path, avoiding obstacles in a 2D plane

The Scenario You are given a matrix of size m x n (width x height) with m*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can ...
0
votes
2answers
133 views

Check if path exists directed graph, without using collection

I have written code to find whether the path exists between source and destination in a directed graph. I have used BFS and instead of ArrayList or queue. I have ...
6
votes
1answer
748 views

Shortest knight path

In preparing a review of this question, I decided to rewrite the code from scratch using a more object oriented approach as I suggested in my review. To recapitulate the problem statement, we are ...
3
votes
1answer
178 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: ...
6
votes
1answer
325 views

A* algorithm in C# for use in a game

I recently started up again on a 2D game engine I have been working on over the last couple of years. I managed to implement a version of the a* algorithm that seems to work fine for my game, but it ...
9
votes
1answer
8k views

Path finding algorithm using recursion in Python

Here is a code I developed some time ago. I wonder if there is anything I can do to improve it. It works for non-loopy mazes which was already my goal. In the maze defined, ...
1
vote
2answers
2k views

Traversing a stack in my DFS algorithm for finding a path in a maze

I am trying to get this code running as fast as possible when traversing through my stack of my DFS currently the input files are like so: ...
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. ...
8
votes
1answer
268 views

Attempt at Dijkstra's algorithm

I tried to implement Dijkstra algorithm in C++ 11. Is this a good implementation of Dijkstra algorithm in C++ or not? I have overloaded -= and ...
3
votes
2answers
551 views

Dijkstra's algorithm in Clojure

I'm learning Clojure and I'm interested in areas that could be more idiomatic. The main function is below. If you're interested in the whole lib, check out this. The function operates on a ...
17
votes
6answers
9k views

“Simple” pathfinding algorithm

I decided to write a pathfinding algorithm in order to expose myself to the world of pathfinding and for me to further understand more advanced algorithms such as A*. I chose C# due to its flexibility ...
6
votes
3answers
1k views

Handling a maze in JavaScript

Is there a way to shorten the conditional statement below? As you can see, there's a lot of repetition. Is the if-statement the best approach here? Bearing in mind ...
3
votes
2answers
146 views

2D A* Path-Finder

I have re-coded my entire path-finding class, it used to follow Dijkstra's Algorithm, while also being super inefficient, using Lists and a lot of other bad things that I had/have no idea about. ...
5
votes
1answer
180 views

Comparing puzzle solvers in Java

I have this program that solves a \$(n^2 - 1)\$-puzzles for general \$n\$. I have three solvers: BidirectionalBFSPathFinder ...
0
votes
1answer
77 views

Groovy pathfinding algorithm

I have created a bit of path-finding code in response to this code golf question. Since this is one of my first large bits of code in Groovy that I have written, I would like to see how I could ...
3
votes
1answer
2k views

BFS for modified shortest path

Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ? The itinerary of each ...
8
votes
1answer
1k views

“Dungeon Game” solution

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially ...
2
votes
1answer
902 views

Shortest path from U to V using at most k nodes

I'm trying to solve a problem that asks for a shortest path between two cities with at most k nodes. The first line of input has the number of test cases. On the second line 3 integers are given, ...
6
votes
1answer
487 views

Live Graphical Demonstation of a Breadth-First Search Algorithm

As a first step to making a PacMan clone, I wrote a Breadth-First Search demonstration that updates itself live as you draw walls and drag around the start and end points. It was inspired by the site ...
4
votes
1answer
4k views

Shortest path on a maze with keys and doors

The locks of the doors present in the maze are of 7 types: A, B, C, D, E, F and G. There are also some copies of keys around the maze, which can be of types a, b, c, d, e, f or g. A key of type a ...
-1
votes
1answer
365 views

2D A* path finder

How can I improve the speed of this path finder A* implementation? ...
3
votes
0answers
2k views

Brute force shortest path in Java

I had to ask myself a couple years ago: before Edsger Dijkstra invented his famous shortest path algorithm, how brute force approach would seem. Below is my version. It's super slow, but I find it ...
4
votes
2answers
1k views

Maze solver for 2D matrix in Ruby

I got rejected for a junior Ruby job entry where I had to solve a 2D matrix as a maze with walls. This is the main class: solver.rb ...
5
votes
2answers
4k views

Path sum in binary tree

Root to leaf path sum equal to a given number Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given ...
2
votes
0answers
830 views

A simple graph walk interception algorithm in Java

I have that girl whose graph walk I want to intercept, but because I am not good at running algorithms in my head, I had to program my computer to do that for me. I would not consider the problem to ...
0
votes
1answer
808 views

A* pathfinder in C

Now I have this implementation of A*. Basically it is the same as the Dijkstra's algorithm in my previous post, yet I bothered to make it more cohesive by making functions for handling all the state ...
4
votes
1answer
831 views

Dijkstra's shortest path algorithm in C

Now I have this C implementation of the famous algorithm: dijkstra.h: ...