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.
6
votes
1answer
92 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
37 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 ...
3
votes
1answer
28 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
...
4
votes
1answer
94 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 ...
141
votes
4answers
21k 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
53 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 ...
4
votes
0answers
29 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
55 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
212 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
90 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
175 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 ...
0
votes
1answer
52 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
102 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
550 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
210 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, ...
6
votes
3answers
1k 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
370 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
96 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
43 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
85 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
79 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
133 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 ...
2
votes
1answer
157 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
19 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
176 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
144 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
156 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 ...
0
votes
0answers
57 views
Finding shortest paths in a Wikipedia article graph using Java - second attempt
I have improved Finding shortest paths in a Wikipedia article graph using Java.
Now I have this:
AbstractWikipediaShortestPathFinder.java:
...
4
votes
1answer
156 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
106 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
331 views
3
votes
1answer
422 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
122 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
311 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
419 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
71 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
218 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 ...
2
votes
1answer
111 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
195 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
2k 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
543 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
347 views
k-shortest path algorithm in Java
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.
My implementation follows:
...
7
votes
1answer
145 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
233 views
Djikstra'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 ...
14
votes
6answers
685 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
889 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
102 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
109 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
47 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 ...
2
votes
1answer
360 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 ...
