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
4
votes
1answer
55 views

Navigating the robot by finding the shortest way

I have this task where I have to make my robot find the shortest way when I enter a destination point. I've created some functions to assign numbers (distances) for each square and counts its way back ...
10
votes
2answers
984 views

Implementation of Dijkstra's algorithm in Python

I have implemented Dijkstra's algorithm for my research on an Economic model, using Python. In my research I am investigating two functions and the differences ...
6
votes
1answer
161 views

Python: Astar algorithm implementation

I have implemented Astar algorithm for a problem on an online judge relating to maze given start and end positions along with a grid representing the maze. I output the length of the path along with ...
5
votes
1answer
48 views

A* and ALT pathfinding in C tips

I adding some pathfinding to a game I'm working on. It primarily used A* with as suggested in the pathfinding articles at reb blob games. It works, but isn't very fast. It is a square grid map that (...
6
votes
2answers
168 views

C#: A* pathfinding - performance and simplicity

Yet another implementation of A* pathfinding. It is focused on: Performance (both speed and memory allocations). Readability and simplicity. Well defined objects and methods. Accordance with general ...
4
votes
2answers
61 views

Speed Up Flow Field Algorithm?

I am slowly creating a flow field pathfinding solution for Unity3D. I'm trying to follow Elijah Emerson's description, which appears in the book 'Game AI Pro' (volume 1). In this question I ask about ...
3
votes
1answer
54 views

Coordinates Struct for Flow Field Pathfinding… am I doing this right?

I am slowly creating a flow field pathfinding solution for Unity3D. I'm trying to follow Elijah Emerson's description, which appears in the book 'Game AI Pro' (volume 1). The map is divided into ...
4
votes
0answers
56 views

I wrote my first pathfinding algorithm

I'm currently writing a small game in Lua, using the Love2d framework. I guess I'm doing it as a practice of sorts, but it did give me the opportunity to write my first pathfinding algorithm. I wrote ...
1
vote
1answer
82 views

Sum of all Paths in Binary Tree

Problem For the given binary tree return the list which has sum of every paths in a tree. i.e Every path from root to leaf. I've written following solution. ...
1
vote
0answers
49 views

Directed graph and Dijkstra algorithm using heap

I have implemented directed graph and Dijkstra algorithm using heap in Python. I first implemented an abstract base class WeightedGraph, of which ...
5
votes
2answers
73 views

Performance Enhancement of A Star Path Finder algorithm with 1024 multidimentional array

I have the below code for a A* pathfinder, however it is taking upwards of 10 minutes to find a solution using a simple 1024 x 1024 array. I had to comment out ...
1
vote
0answers
26 views

Python3 BFS Flood Fill with Deque and 2D Indexing

I'm currently in a programming competition where time is key, therefore I'm trying to optimize my solution as much as possible. I am trying to implement a BFS Flood Fill solution on a map size of ...
4
votes
2answers
64 views

Bellman Ford algorithm using vector

I have written this code for bellman-ford algorithm. Please review and suggest improvements: This code takes input graph as an adjacency matrix, and stores it the ...
4
votes
1answer
79 views

A* pathfinding for integer Vectors

This class is for calculating the shortest path in a 2D World (without minding obstacles). I'm using the A* algorithm and 2D Vectors (from the SFML Framework). It is working but takes (a lot of) time ...
4
votes
1answer
33 views

Advice on path-finding visualisation program

Im looking for some help on improving my code which visualizes path-finding algorithms. The code is working however I know it can be improved. Any suggestions would be appreciated. Github code - ...
4
votes
2answers
188 views

Dijkstra Algorithm implementation in C++

I have implemented Dijkstra's algorithm in C++, but it seems a bit complicated since I really tried to follow the process of the algorithm as much as I could. If there's any simplification you would ...
11
votes
2answers
281 views

Path finding solution for a maze whose state changes during the solve

This is not a traditional maze where you find the shortest path (like the gif on the left). In order to solve it, you need to visit every available node before reaching the end, where once a node is ...
2
votes
2answers
67 views

A-Star for 2D Graph (not grid)

This is my A-Star implementation for a 2D space of nodes but allowing to specifically set connections between nodes because my usecase does not have points tied to a grid (however for clarification ...
3
votes
1answer
67 views

A Brushfire algorithm to generate a distance map in a grid

I'm working on implementing a goal-based pathfinding. first step is to set a goal and calculate the shortest walkable distance between the goal and all points in the grid, using a brushfire algorithm. ...
7
votes
2answers
308 views

Find the closest enemy in a 2D grid with wrapping allowed

I'd like feedback on my solution to the outlined programming challenge. Is numpy a good candidate module for this? What might be a more efficient or Pythonic solution? Closest Enemy II Have ...
5
votes
1answer
131 views

Speeding up Dijkstra's algorithm

I have Dijkstra's algorithm: ...
7
votes
2answers
1k views

Find the correct path through a 5 x 5 grid (coderbyte 'Correct path')

I've completed the following coderbyte question and would like feedback as to whether it follows Python best practices, is efficient and so forth. The coderbyte problem: Have the function ...
2
votes
0answers
35 views

Codewars: Remote Control Virtual Keyboard

This is my solution to the Codewars problem TV Remote (symbols). Description In short, you are given a virtual keyboard with 3 modes between which can be switched by pressing the ...
2
votes
1answer
226 views

ROS implementation of Dijkstra's algorithm to shortest path

I am making a ros node to implement dijkstra's algorithm on a 1000x1000 pixel map. I have used map_server to convert the map into an nav_msgs/OccupancyGrid. The map is in the form of a row dominant ...
8
votes
2answers
3k 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 : ...
2
votes
0answers
27 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: ...
3
votes
0answers
54 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: ...
7
votes
1answer
144 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 (...
4
votes
1answer
97 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: ...
5
votes
1answer
214 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
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 ...
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
75 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
1answer
124 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
53 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
85 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 ...
3
votes
0answers
124 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 ...
2
votes
1answer
39 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
265 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
424 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
65 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
103 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
92 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
197 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
6k 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
169 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
212 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
157 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
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 ...
6
votes
1answer
396 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 ...

1
2 3 4 5