# 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.

197 questions
Filter by
Sorted by
Tagged with
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 : ...
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, ...
90 views

### Minimum amount of edges that needs to be traversed to visit all vertices… or something like that

So I have this problem, where I'm given m connections over n vertices. The vertices are labeled ...
66 views

### Shortest Cell Path In a given grid

I was given this problem in a mock interview. I would appreciate a review of my implementation. Shortest Cell Path In a given grid of 0s and 1s, we have some starting row and column sr, sc and a ...
52 views

### Fast algorithms in Javascript for shortest path queries in directed unweighted graphs

(There is a follow-up question available to this: Follow-Up Question) So I have this: ...
24 views

### Fast algorithms in Javascript for shortest path queries in directed unweighted graphs - follow-up

(See the previous iteration.) Now I have reworked my pathfinder program, and I ended up with this: ...
112 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 (...
222 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. ...
6k 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 ...
4k 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 ...
436 views

### Dijkstra'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 ...
51 views

### Maze algorithm to find path between points

I am creating an algorithm to find the shortest path between two points in a maze but my current solution is too slow. This is what I did: Helper classes: ...
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 ...
1k views

### Fastest path on a snakes and ladders board

I am not looking for a detailed review of this code as I am aware it is very inefficient. The main reason for posting this is to see if there is a better way to achieve my goal (I am certain there ...
112 views

### Shortest pathway across a snakes and ladders board (Update)

Earlier I posted a fairly inefficient recursive solution to the problem of getting across a snakes and ladders board in the smallest number of moves. I have created a much faster solution to this ...
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 ...
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 ...
60 views

### Faster k-shortest path algorithm in Java

In the $k$-shortest path problem, we are searching for (at most) $k$ distinct, shortest paths connecting two given terminal nodes. You can see the previous version here. This implementation, ...
2k views

### k-shortest path algorithm in Java

(See the next iteration.) 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. ...
116 views

### Implementation of Dijkstra algorithm

I am trying to implement Dijkstra algorithm. I try to calculate cost of reaching every node from first node. Though I have tried with couple of graphs and results are correct but I have one doubt ...
8k views

### Simple maze solving algorithm

I was to write a simple maze solver program that takes in an input file denoting the maze start and end points, and the structure of the maze itself. The specifications were to keep it as simple as ...
49 views

### Lowest cost path through elements in a matrix

I've developed a program in Python that calculates the lowest possible costing path between two points in a matrix, including the values contained in the start and finish cells. The code is below. ...
59 views

### Maximize Path Value

I recently had to code an algorithm that will, for an input of: matrix of up to 5x5 size and a defined path length, find a path of this given length from the first top left matrix element (0, 0) to ...
139 views

### Python A Star with fewest turns and shortest path variations

I had a lot of fun writing these. I haven't seen a version minimizing turns, so that was a neat challenge. Any suggestions are very welcome. Is there anything to gain by making more method variables ...
35 views

### Uni- and bidirectional pseudo-generic shortest path finders in C89

I have implemented two related shortest path algorithms for unweighted graphs in C89. My attempt was to learn some more idiomatic C constructs such as genericity (a client programmer should be able to ...
237 views

### Graph puzzle resolver

I've solved test task for job vacancy. Need your feedback about my solution. Task The image below shows the puzzle in the solved state. The puzzle consists of 10 cells. Among the cells one is empty, ...
362 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,...
202 views

### AI to avoid obstacle

The AI I'm making is really simple, however it might be a bit too inefficient for what it is doing. The chart below shows speed differences between various arithmetic and math operations. ...
91 views

### Maze navigator AI

I developed a maze navigator in Java for a project for my school. It works fine, and it gets through the maze just fine. The program prints to the screen each time it loops through the maze to set the ...
148 views

### Bidirectional iterative deepening pathfinding algorithm in Java

Introduction I have this iterative deepening search algorithm. The main "research" attempt was to find out a bidirectional version of that search, and it turned out to be superior compared to two ...
78 views

### Project Euler #81 in Haskell: minimal path sum through a matrix

I just completed Project Euler Problem 81 in Haskell: In the 5 by 5 matrix below, ...
4k views

### Find the shortest path between two points in a 2D matrix with obstacles

I need to find shortest path between two points in a grid given an obstacles.. Given a 2 dimensional matrix where some of the elements are filled with 1 and rest of the elements are filled. Here ...
85 views

### Finding valid path on 2D Grid

I got a 2D grid (n x n matrix). The user selects his player in this 2D grid and after that selects another node in this grid to mark his destination position. The player is allowed to move ...
2k views

### Java breadth-first search for finding the shortest path on a 2D grid with obstacles

Please review my Breadth-first search algorithm implementation in Java for finding the shortest path on a 2D grid map with obstacles. The findPath() method ...
5k views

### Shortest path in a grid between two points

I have this problem where I have to find the shortest path in an NxM grid from point A (always top left) to point B (always bottom right) by only moving right or down. Sounds easy, eh? Well here's the ...
233 views

### Maze solver BFS in Haskell

I am really excited that I just wrote my Haskell maze solution in bfs. This is my very first haskell (and I still haven't tried to build a maze in haskell so that maze is hard coded xD) ANY ...
37 views

### Modular graph searcher

some words in forehand: Unfortunately this post is very long, thus I decided to put the whole and compilable code into an online compiler. The link is at the end of this post. In the last few days I ...
73 views

### Mapping a robot's obstacles based on its position and sensor data

I have a grid in which I'm adding different cell-blocks to, depending on what rotation I'm currently receiving. @@@ = Map border ...
136 views

### Latitude/Longitude graph optimised A* Algorithm

Can anyone point me in the direction of a C# or pseudocode implementation of A* optimised for relatively sparsely connected graphs (average < 3 edges per node)? ...
90 views

### BFS Pathfinding algorithm using Javascript generator

I'm implementing a BFS traversal in a grid-like structure. Because I wanted to experiment with ES6 Generators for a long time, I thought I'd implement the search using that abstraction. I am sure ...
474 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 ...
2k views

### 2D Maze solver using recursion in Python

A company I interviewed for sent me a coding problem to solve. The problem was to find a solution to a maze, not necessarily the shortest one. The input would be like so: ...
891 views

### Java Pathfinding Lee Algorithm

For my Pacman game i need to implement a pathfinding algorithm. I decide to do it with the Lee Algorithm, because in my opinion it's easier to understand than e.g. A* Star algorithm. I tried to ...
3k views

### A* Algorithm in C# for pathfinding 2D tile grid

I am very new programming and am trying to develop a small tycoon game as a hobby project in Unity. This algorithm executes beautifully but if 100+ agents are getting new paths simultaneously there is ...
4k 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 ...
1k views

### Finding all possible paths between two points in a grid using recursion

I'm trying to find all possible paths made of 0 from bottom left to top right, only by moving either up or to the right. The input file contains a grid of characters, where ...
53 views

### A component to find a path to a certain node

Recently I started fiddling around with pathfinding. I created a WayPoint component to determin a possible way to another actor which is defined over other waypoints. My grid is looking somewhat like ...
406 views

### Bidirectional BFS on a matrix in Python 2.7

This code is a bidirectional BFS search. Given any two points in a matrix having 0's and 1's, I would like to find if there exists a path between them. Also note that it is forbidden to enter a cell ...