We’re rewarding the question askers & reputations are being recalculated! Read more.

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
4
votes
1answer
4k views

A* (A-Star) pathfinding algorithm with dynamic node generation in Python

I wrote code which implements the A* algorithm in Python. A* is a shortest path algorithm which resembles Dijkstra's Algorithm, but includes an estimator to guide the search. The pseudocode of both ...
1
vote
0answers
81 views

Any-angle path planning

I implemented a highly generic version of the Theta* algorithm. I know, it's genericity leads to a very complex usage up to complete non-usability, see example below. The algorithm: ...
3
votes
1answer
2k views

C++ Dijkstra's shortest path implementation

I have created a c++ function that searches for the shortest path between two points with dijkstra's shortest path algorithmus. I'm using it right now in combination with a program that solves mazes ...
6
votes
1answer
614 views

Pathfinding library in C++ with fluent API

Introduction I have this C++ pathfinding library. My primary requirement is that a client programmer may couple his/her own graph representation and the library will work with that representation. ...
12
votes
3answers
6k views

Maze solver and generator in Python

After watching Computerphile's video I decided to create my own maze solver and generator in Python. I've never written anything in Python so I'd like to get some feedback about my code, specifically ...
1
vote
2answers
250 views

A* Algorithm implementation

This is an implementation of A* algorithm, that I will use in my game. Navigation.hpp ...
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). ...
5
votes
2answers
289 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 ...
2
votes
1answer
684 views

Google Foobar challenge: Exiting a space station maze, where one wall may be removed

I'm solving Foobar challenge. My code runs perfectly in eclipse but when i verify it on foobar it says Execution took too long . The question is - You have maps of parts of the space station, each ...
4
votes
1answer
1k views

Python: AStar Pathfinder algorithm

Traverse through any binary array using the Manhattan distance by giving a start node location and an end node location. The neighbor() method gives the neighbors next to the x,y coordinates that are =...
2
votes
0answers
505 views

Routing simulation (Distance vector)

I am trying to write simulation for routing algorithm by distance vector. I will explain my class and how it works a bit, and then, introduce three main issues I encouter. Important to mention that ...
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 ...
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)\$, ...
4
votes
1answer
105 views

Path Finder Maze

The goal of my code was to find all possible moves from each open position in the maze (@moves_hash), assign it a value for how many moves it would take to get to ...
8
votes
1answer
4k views

Find the shortest path through a maze with a twist: you can knock down one wall

I would like my solution to Google Foobar's prepare_the_bunnies_escape checked for readability, maintainability, extensibility, style, design. I am looking forward ...
3
votes
1answer
53 views

Assign variables to save each directories from a folder

I want to assign corresponding variables based on the name to save each directory from a folder, including its subfolders, so I can get access to the file in each folder easily. The code created by ...
2
votes
1answer
227 views

A* path finding getting the node neighbors

Is there any way I can minimise this code.The code will get the neighbours of the current node and point the arrow to the current node ...
5
votes
1answer
6k views

Shortest Path For Google Foobar (Prepare The Bunnies Escape)

I have been working on Google Foobar since a few days ago. I am currently in the third level but is stuck in the second challenge of "Prepare the Bunnies' Escape." I have checked this post but it did ...
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 ...
2
votes
1answer
62 views

Finding a path across a grid after randomly filling some proportion of it

Essentially, we must be able to get from one side of the grid to the opposite side of the grid. My code tests for up to down and left to right. However, this is painfully slow and I'm wondering if ...
3
votes
0answers
102 views

F# implementation of the A* algorithm round 2

This is my second attempt at implementing the A* algorithm using F#, the first one is here. What I changed: I removed the Node class and added two records named ...
3
votes
1answer
176 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 ...
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 ...
6
votes
1answer
412 views

Shortest Path (BFS) through a maze

Background I have decided to use this year's Advent Of Code to learn Haskell. I feel like I vaguely understand the language and can solve most of the problems with relative ease. However, the code I ...
0
votes
1answer
614 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 ...
1
vote
1answer
845 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: ...
1
vote
1answer
776 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 =...
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 ...
9
votes
2answers
976 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
7k 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 ...
6
votes
1answer
5k 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
221 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
61 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
185 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
481 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
1k 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 ...
3
votes
1answer
4k 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
540 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
512 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
569 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
159 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 ...
1
vote
1answer
5k views

Shortest path in maze

Please help review my code. ...
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 ...
3
votes
1answer
235 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
105 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
682 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 ...