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.

learn more… | top users | synonyms

1
vote
0answers
13 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
87 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
67 views

Shortest path in maze

Please help review my code. ...
3
votes
1answer
99 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
96 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
63 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
156 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
60 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
90 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
79 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
159 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
267 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
163 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
169 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
126 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
175 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
447 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
864 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
97 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
80 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
37 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
205 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
161 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
158 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
68 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
116 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
223 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
69 views

2D A* path finder

How can I improve the speed of this path finder A* implementation? ...
1
vote
0answers
285 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
356 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
769 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
181 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
134 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
83 views

Dijkstra's shortest path algorithm in C

Now I have this C implementation of the famous algorithm: dijkstra.h: ...
12
votes
1answer
667 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
428 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
220 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
247 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
359 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
236 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
160 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
240 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
85 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
57 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
253 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
84 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
120 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
113 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
67 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 ...