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.

5
votes
1answer
79 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 ...
5
votes
2answers
903 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 ...
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 ...
2
votes
0answers
41 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, ...
1
vote
2answers
103 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 ...
3
votes
0answers
33 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. ...
2
votes
1answer
46 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 ...
2
votes
1answer
28 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 ...
5
votes
1answer
224 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, ...
15
votes
3answers
329 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,...
6
votes
1answer
60 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 ...
3
votes
1answer
79 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 ...
2
votes
0answers
73 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, ...
3
votes
1answer
99 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 ...
1
vote
0answers
3k 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 ...
1
vote
0answers
119 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 ...
5
votes
2answers
194 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. ...
2
votes
1answer
72 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 ...
3
votes
1answer
1k 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 ...
4
votes
1answer
160 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 ...
4
votes
0answers
34 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 ...
5
votes
1answer
110 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)? ...
0
votes
1answer
68 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 ...
8
votes
1answer
324 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 ...
4
votes
1answer
1k 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: ...
2
votes
1answer
650 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 ...
5
votes
1answer
2k 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 ...
2
votes
3answers
699 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 ...
0
votes
2answers
49 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 ...
4
votes
1answer
339 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 ...
2
votes
0answers
43 views

Shortest path via intermediaries

Created a shortest path finder that must pass via sets of intermediary edges (either one in each set counts as a pass) in order. Primarily I would like to know if there are logical fallacies in the ...
7
votes
0answers
1k 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 ...
3
votes
2answers
374 views

C# A* Pathfinding implementation, focusing on reusability and efficiency

I wrote a C# A* pathfinding (Though, it's generic enough that it could be used for other search purposes) implementation. I started this when I found that existing implementations often didn't support ...
2
votes
3answers
753 views

Find the longest path in a matrix where each step has entries that differ by 1

Given an N*N matrix that all numbers are distinct in it, the function should find the maximum length path (starting from any cell) such that all the cells along the path are in increasing order with a ...
4
votes
1answer
6k 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 ...
4
votes
1answer
119 views

2D discrete motion planner

I am writing a 2D discrete motion planner for a task with specific instructions. The instructions for the search algorithm are contained entirely in the docstring for the ...
2
votes
1answer
528 views

Wall-following program

I'm taking an AI Class and I managed to get my algorithm to work it's not complex since the robot is surrounded and placed by the wall. However, in my opinion, the code doesn't look so clean and I ...
1
vote
0answers
43 views

Controllable graph search in Java

This program is not that much about graph search as it is about a design pattern that allows us to decide how much time we may invest in searching for a path. Here's the code: BreadthFirstSearch.java ...
3
votes
0answers
79 views

Best path using some intermediate points, where cost is either x-axis or y-axis distance

We are given N Cartesian points \$(x, y)\$. Anytime we move from \$i\$-th point to the \$j\$-th, the move costs \$\min\left(\left|x_i - x_j\right|, \left|y_i - y_j\right|\right)\$. The problem is to ...
2
votes
0answers
88 views

Find a (nearly) optimal route among several locations that can be found by Google Maps

The README should give you all of the information you need for a comprehensive review, and if it doesn't then please say so. If you would like to contribute a review but do not have time or desire to ...
3
votes
2answers
201 views

Distance Field Generation Algorithm

I'm working on a vector field pathfinding algorithm. So far I have everything working but my distance (potential?) field takes some time to generate (given that I'm generating for a very large grid ...
5
votes
1answer
76 views

Horse trying to find path

I'm trying to get good at JavaScript and I wrote this code in order to make mistakes and learn better ways to do it. It's a silly UTF-8 horse trying to find its way towards the flag. You can check it ...
1
vote
2answers
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 ...
4
votes
1answer
473 views

Uni- and bidirectional beam search in Java

What Beam search is a best-first search algorithm that does not necessary find an optimal path, yet has smaller memory-footprint. In this program, I attempted to answer a question how does it compare ...
4
votes
1answer
3k views

A* (A-Star) pathfinding algorithm with dynamic node generation in Python

I wrote code which implements the A* algorithm in Python. A* is a shortest path algorithm which resembles Dijkstra's Algorithm, but includes an estimator to guide the search. The pseudocode of both ...
1
vote
0answers
77 views

Any-angle path planning

I implemented a highly generic version of the Theta* algorithm. I know, it's genericity leads to a very complex usage up to complete non-usability, see example below. The algorithm: ...
3
votes
1answer
2k views

C++ Dijkstra's shortest path implementation

I have created a c++ function that searches for the shortest path between two points with dijkstra's shortest path algorithmus. I'm using it right now in combination with a program that solves mazes ...
6
votes
1answer
554 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. ...
12
votes
2answers
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 ...
1
vote
2answers
204 views

A* Algorithm implementation

This is an implementation of A* algorithm, that I will use in my game. Navigation.hpp ...