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
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 ...
28
votes
4answers
75k views

A* search algorithm

NodeData stores all information of the node needed by the AStar algorithm. This information includes the value of ...
23
votes
3answers
14k 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, ...
16
votes
6answers
7k 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 ...
15
votes
3answers
355 views

Traversing an infinite graph using Dijkstra's algorithm to maximize cookie production speed

Imagine the following situation: It is the year 20XX. You are a prodigious baker, capable of baking cookies at an astonishing rate of 1 cookie per second. Your archnemesis, an equally excellent baker,...
14
votes
8answers
8k 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 ...
13
votes
2answers
8k 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 ...
13
votes
1answer
2k views

Path finding function

Could this be made more efficient, and/or simpler? It's a path-finding function. It seems to work, but do you see any potential cases where it could fail? ...
12
votes
3answers
5k 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 ...
12
votes
2answers
4k 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 ...
12
votes
1answer
620 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 ...
12
votes
1answer
3k 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 ...
11
votes
2answers
11k 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. ...
11
votes
3answers
806 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 ...
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 ...
11
votes
3answers
979 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 ...
10
votes
4answers
2k views

Maze generation

I have been working on a maze generator in C++ in an effort to learn the language and brush up on some long lost knowledge. I want to ensure that I am using best practices, and really doing things the ...
10
votes
2answers
5k 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 ...
10
votes
2answers
823 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 ...
9
votes
5answers
2k 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 ...
9
votes
1answer
7k 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, ...
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, ...
8
votes
7answers
6k 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 ...
8
votes
2answers
5k views

How can I improve upon my A* Pathfinding code?

How can I make it faster, more efficient, and simpler? Are there any obvious mistakes I've made, or things which will make my code "fancier"? It's my first time working with any form of pathfinding, ...
8
votes
2answers
2k views

Implementation of A* algorithm in C++

I have implemented the A-Star path finding algorithm for a 2D grid. The function returns a list of positions of an acceptable path. main.cpp : ...
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 ...
8
votes
1answer
254 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 ...
8
votes
1answer
456 views

Google FooBar “Prepare The Bunnies Escape”

I'm currently working through the google FooBar challenge, and I'm on the third level, in which I have to find the distance between the top left and bottom right points on a grid. The grid is filled ...
8
votes
1answer
1k 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 initially ...
7
votes
3answers
2k 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 ...
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 ...
7
votes
4answers
20k 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. <...
7
votes
1answer
1k views

Python program to find a word ladder transforming “four” to “five”

I saw this Puzzling problem and thought I would try to write a Python program to solve it. The task is to transform "four" to "five", forming a new four-letter word at each step, replacing one letter ...
7
votes
2answers
817 views

Path finding - again

Nearly time to hand this project in, and I want it to be as close to perfect as possible. So, any issue (no matter how small) - let me know. If you have any ideas that would improve the efficiency or ...
7
votes
1answer
475 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 ...
7
votes
1answer
106 views

Random Maze Pathfinder

I just finished a huge project of mine; a maze pathfinder. At the start, the maze that the program is traversing is randomly generated, with a 25% change to place a wall (...
7
votes
1answer
2k views

Minimum cost path of matrix using Python

I was reading this article about finding the minimum cost path from (0,0) to any (m,n) point in a matrix. Using python the ...
6
votes
3answers
1k 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 ...
6
votes
1answer
2k 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 ...
6
votes
1answer
119 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 ...
6
votes
2answers
749 views

A* path finding algorithm for a red-black tree

So far I've implemented a way to add to my RedBlackTree (will be used with A* pathfinding - hence the F value). I'm not entirely sure how to improve it further. I ...
6
votes
1answer
183 views

CoffeeScript implementation of A* algorithm

...
6
votes
1answer
454 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 ...
6
votes
1answer
610 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. ...
6
votes
1answer
411 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 ...
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 ...
6
votes
1answer
303 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 ...
6
votes
1answer
62 views

Optimal algorithm to move a a rope from one position to another

I'm an engineer working with a deformable membrane that is attached to actuators. The goal is to move the membrane from one shape to another, without ripping the membrane. This imposes "neighbor ...
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-...
5
votes
3answers
596 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 ...