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

5
votes
3answers
338 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 ...
10
votes
0answers
76 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 ...
-1
votes
1answer
39 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
100 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
159 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
127 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
64 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 ...
5
votes
2answers
73 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
45 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
172 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
43 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
67 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
50 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
63 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
51 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
75 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
195 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
127 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 ...
3
votes
2answers
69 views

A* versus Bidirectional Dijkstra's algorithm

I have added bidirectional Dijkstra's algorithm into my pathfinding "framework", and I would like to make good use of C++ programming idioms, eliminate all possible memory leaks, otherwise improve ...
2
votes
1answer
65 views

Generic pathfinding framework in C++

I have this generic framework for finding (weighted) shortest paths. Also, the program demonstrates the performance of A* and Dijkstra's algorithms on a directed weighted graph. Both run in ...
3
votes
1answer
69 views

Yet another graph search

I noticed there were already countless implementations of graphsearch procedures on here, but there were a couple of features of my approach that I haven't seen in the others, plus I would greatly ...
4
votes
1answer
282 views

Shortest path through a maze

I was trying to solve this problem in Java: Given a 2-D array of black and white entries representing a maze with designated entrance and exit points, find the shortest path from entrance to exit, ...
3
votes
2answers
341 views

BFS Maze Solver in Scala

I recently got a Scala developer position, so I'd like to get more comfortable with Scala on my own. Here is a maze solver that I wrote (previously in other languages) that I translated to Scala. Any ...
3
votes
1answer
218 views

N-puzzle program solved using A* search

I coded the following program to solve the n-puzzle problem with n = 3. Are there any suggestions regarding readability and variable names? ...
2
votes
2answers
152 views

Finding the shortest path through a 2d space with a display

I decided to implement most of the reddit Daily Programmer space probe challenge. My program creates a 2D space that have asteroids and gravity wells distributed (the percentage of gravity wells and ...
2
votes
1answer
81 views

Small generic path search framework in Java

I have this small generic path search library. It's not perfect at all, so I need some comments as to have a chance to improve it. com.stackexchange.codereview.graph.model: ...
6
votes
4answers
2k views

Python 8-Puzzle and solver

I wrote a simple 8-Puzzle and solver and am interested in seeing how it might be improved. Please let me know if any style or design changes might enhance the readability/performance of my code. ...
6
votes
1answer
102 views

Performance of A* route

I'm new to the Swift language. I have a C# version of a simple A* route which is very fast. But I rewrote it with Swift, and the performance is very bad (3,4 seconds for a very simple road). Could ...
3
votes
1answer
159 views

Djkistra shortest path implementation for adjacency list represented graph

Please review the implementation of Djkistra algorithms. Points on which I have doubt: My Graph doesn't have any ID for nodes. Nodes are accessed based on their ...
11
votes
3answers
369 views

Finding shortest paths in directed graphs

I have very little experience in programming with C++ and the following small "program" is the 2nd one I have ever written in that language. I am most interested in comments regarding naming ...
0
votes
3answers
891 views

Dijkstra in C++ to find shortest path for every vertex of a directed graph

I am trying to implement the Dijkstra algorithm in C++ that finds the shortest path for a graph from a text file. The text file contains a matrix that represents a directed graph. What I am trying ...
5
votes
2answers
570 views

Tremaux Algorithm

I am trying to implement Tremaux Algorithm for a 2D maze. So far the robot works well however I have some problems with retraceStep(). I'm not asking how to ...
2
votes
1answer
717 views

Finding the shortest path in a graph

Could you please advise on the code and its design? Is there any way I can apply object oriented principles to make the design robust yet flexible? ...
5
votes
2answers
472 views

More optimized approach of Dijkstra's algorithm

I need a graph-search algorithm that is enough in our application of robot navigation and I chose Dijkstra's algorithm. We are given the gridmap which contains free, occupied and unknown cells where ...
11
votes
2answers
930 views

Contest code for a maze problem

I would like to ask your comments on my contest code for the following problem: We're going to have a slightly more logical puzzle today. We're going to write a program that will find a path through ...
2
votes
1answer
51 views

Is this Python pathfinder efficient enough?

I'd like to see if my code follows common practice, or is already efficient or fast enough. ...
4
votes
1answer
257 views

Finding Shortest Path

Working on Functionally Solving Problems from Learn You a Haskell, I worked on the "Heahtrow to London" shortest path problem. I'm working on a reduced set of this problem in order to solve a simple ...
10
votes
3answers
236 views

Optimization of aStar in Java

I'm currently looking to optimize my aStar algorithm as my last run through took roughly a minute to generate one path. I've never had to optimize before as I've never run into performance issues, so ...
2
votes
1answer
111 views

Retaining depth information and recursive traversals

I have been using the pattern below for some time and it has worked well, but more than once I have almost bled my brain out of my ear trying to keep track of: the recursion depth the recursion path ...
6
votes
1answer
591 views

Escaping the prison - finding the shortest way

I have given an assignment where I have to escape a labyrinth. The goal is to find the shortest way. I have done some research and there seem to be two strategies to solve the problem: the Depth-first ...
10
votes
2answers
4k views

Recursive maze solver

Up for review today is some C++11 code to recursively search a maze for a path to a specified goal. This one shows dead-ends it explored on the way to finding the solution. ...
3
votes
2answers
367 views

Recursive uniform cost search that needs to be optimized

I have this uniform cost search that I created to solve Project Euler Questions 18 and 67. It takes the numbers in the txt file, places them into a two dimensional list, and then traverses them in a ...
13
votes
8answers
7k views

Is my AI solution to Untrusted Game considered logical or “ethical”?

I am applying to a university to study Computational Linguistics, and as I read, it would be recommended to have a background in Artificial Intelligence. The Admission board asked me to prepare a ...
8
votes
5answers
1k views

Efficient pathfinding without heuristics?

Part of my program is a variable-sized set of Star Systems randomly linked by Warp Points. I have an A* algorithm working rather well in the grid, but the random warp point links mean that even though ...
10
votes
2answers
248 views

Finding path in Maze

I recently gave an interview and was asked the following question. I posted this here Finding path in Maze also, and someone suggested I should try Code Review. So here it goes. A maze is a group of ...
7
votes
3answers
881 views

Shortest path algorithm is too slow [closed]

I am solving one problem with shortest path algorithm, but it is too slow. The problem is that I have N points and these can be connected only if the distance between them is smaller or equal than ...
4
votes
1answer
238 views

Tilt maze solution

If one does not know tilt maze then the game looks like this. Basically one can travel in 4 directions North, East, South and West, but this travel's endpoint is the furthest non-obstructed block. If ...
10
votes
2answers
1k views

Find a path through a maze

This maze has multiple entry points, and quite obviously multiple exits. The entry or exit is not provided at input. Of the multiple sources and destinations, any single path from any source to any ...
7
votes
6answers
1k views

Getting the shortest sequence to reach a number

I want to get the shortest sequence to reach a number. Rules: A[0] is always 1 Either A[i] = A[i-1]*2 or ...
12
votes
3answers
2k views

Calculate the number of moves requires for a knight chess piece [closed]

It's possible to work out the number of moves required to move from (0, 0) to (A, B) for a knight on an infinite chess board in O(1) time. This is an attempt at a solution to do it in O(n) time, ...