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.
3
votes
1answer
60 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
89 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
46 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
126 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
59 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 ...
5
votes
1answer
62 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
71 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
150 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 ...
7
votes
1answer
148 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
98 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
107 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
125 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
159 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
398 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
861 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
95 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
77 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
36 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 ...
0
votes
0answers
135 views
Floyd-Warshall algorithm and a tiny all-pairs shortest path library in Java
Now I have implemented the Floyd-Warshall algorithm with emphasis on dropping space complexity from \$\Theta(V^3)\$ to \$\Theta(V^2)\$. Also, I tried hard to make the API as logical as possible. What ...
2
votes
1answer
133 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 ...
7
votes
1answer
143 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 ...
2
votes
1answer
63 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
102 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 ...
1
vote
1answer
194 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
68 views
1
vote
0answers
220 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
325 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
...
3
votes
2answers
645 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 ...
2
votes
0answers
167 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 ...
-1
votes
1answer
115 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
77 views
Dijkstra's shortest path algorithm in C
Now I have this C implementation of the famous algorithm:
dijkstra.h:
...
12
votes
1answer
470 views
IDA*: Iterative Deepening A* implementation
I created a generic version of IDA*. I am attempting to create the following code with exceptional quality and performance. I'm hoping to try and create short code tutorials regarding. However, the ...
5
votes
3answers
403 views
SPOJ solution of GRAVITY
I am solving problem GRAVITY on SPOJ. Each test case is a rectangular ASCII grid of dimensions m × n, and you have to determine ...
12
votes
1answer
213 views
Racetrack pathfinding and path following
Racetrack
The August community challenge is to implement a program that plays the Racetrack game. Each player starts with an integer position on a square grid. On each turn, the current player can ...
-2
votes
1answer
226 views
Shortest path in dag saga: Dijkstra's algorithm [closed]
I have this Dijkstra's shortest path algorithm:
net.coderodde.graph.pathfinding.AbstractWeightedPathFinder:
...
12
votes
2answers
254 views
Let's (path) find A Star
Yesterday I found myself struggling with creating an A * algorithm in Java, but this morning I finally figured it out, so I would love to hear what Code Review has to say about it!
The goal here is ...
3
votes
1answer
216 views
Shortest path in image
This code takes an image and detects a global shortest path from the top to bottom row, with the requirement that top and bottom column index be the same. For this, it scans through each element on ...
1
vote
2answers
152 views
A* algorithm in C++
I wanted to know if my A* algorithm is well-implemented and if it could be optimized in any way.
...
5
votes
1answer
188 views
Shortest paths from a single source (Dijkstra and Bellman-Ford)
I did not implement a priority queue in Dijkstra. I'm not sure if a trivial priority queue is the best choice, since, after each iteration, several elements change their value. Maybe it is better to ...
4
votes
2answers
81 views
Obstacle-avoiding AI
I have made a game in Java that involves two players to fight each other with spaceships. For one player mode, I have programmed a simple AI to avoid allies and asteroids and go straight towards the ...
1
vote
2answers
54 views
Simple Grid Builder for Future Maze Applications
I'm new to Clojure and decided to read the book, "Mazes for Programmers". My first task, without reading any of the book, was to think of how I would create a maze. This is my first result and I'd ...
3
votes
2answers
237 views
Memory efficient A* (AStar) Algorithm
I am writing a solved for 15 puzzle game which will find the solution path to any NxN board. For easier boards the algorithm works great solving almost any 3x3 boards, most 4x4 boards, but when I go ...
3
votes
0answers
78 views
Golang A* Pathfinder
This is a generalized A* pathfinder in Go. I am new to the language and am eager for advice about best practices.
In particular, I am not sure if the type assertion I make in ...
2
votes
2answers
114 views
Pathfinding in turn-based strategy game
I am using Python with libtcodpy to build a turn-based strategy game.
In this game each unit has a maximum range which varies from 4-10. This range determines how many "steps" the unit can take and ...
3
votes
1answer
63 views
Crawling 2D Maze/Matrix
I'm trying to create a class that's able to 'crawl' through a generic 2D matrix.
Crawling through a Bitmap (which can be viewed as a 2D Matrix of Colors) should yield the same result of a flood fill.
...
1
vote
0answers
96 views
A* search algorithm in Clojure
Cost of nodes are represented by a matrix (called world), heuristic cost estimate/g score/f score are all represented in matrices.
The world and its size are ...
2
votes
0answers
64 views
AI for depth-first walking in a maze, with variable depth look ahead search for dead ends and finish point
This code is a part of a little game I've started a week ago.
It is too extensive to review at once, so I'm picking the most interesting and crucial parts.
Start with the AI.
It has public update ...
2
votes
1answer
129 views
Doing tree search in Java
I have this tiny library for building unbalanced, binary trees and doing tree search on them. I tried hard to define a generic API that would allow custom implementations of trees.
...
2
votes
2answers
780 views
Finding paths through matrix
Given the problem:
You are given a 2-Dimensional array with M rows and N columns. You are
initially positioned at (0,0) which is the top-left cell in the array.
You are allowed to move either ...
7
votes
1answer
175 views
A* algorithm for hex tiles
I implemented the A* algorithm for pathfinding for a game of mine. The game uses hex rooms which are connected to each other by an int[] in the room class. Are ...
