Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
0 votes
1 answer
211 views

Bellman Ford algorithm for triangular arbitrage in JS

...
Mubashir Waheed's user avatar
4 votes
1 answer
567 views

Multithreading a shortest path algorithm

I would like to modify my shortest path finding code to use multithreading and improve its performance. The algorithm must be able to work with negative weights, and as a result, we cannot use ...
c.leblanc's user avatar
  • 263
6 votes
2 answers
309 views

Bellman-Ford optimisation in C with Shortest Path Algorithm (SPFA) and Small Label first (SLF)

I am trying to code an optimized version of Bellman-Ford algorithm. This post is a continuation of the following post Bellman-Ford optimisation in C in which I posted a first version of the classic ...
c.leblanc's user avatar
  • 263
6 votes
2 answers
2k views

Bellman-Ford optimisation in C

Here is my current code: ...
c.leblanc's user avatar
  • 263
5 votes
2 answers
985 views

Optimizing Python BFS Code

...
FailingCoder's user avatar
1 vote
0 answers
25 views

Figure out all paths of all nodes up to k depth

I'm trying to figure out all the paths of all the nodes up to K depth. It seems to be a dynamic programming problem, my attempt seems to be working however its slower than I expected I would think ...
Ritzy Dev's user avatar
  • 111
1 vote
0 answers
157 views

A-star pathfinding algorithm to route through a raster maze

I have a problem that needs path finding to solve. It is a vector of ints; 1 for passable terrain and 0 for non-passable. My implementation is not fast enough for the test. How could I make it faster? ...
Isak True's user avatar
1 vote
2 answers
201 views

Finding the cheapest path between two points using Dijkstra

I am trying to use Dijkstra to find the cheapest path between two pixels in an image. Implementation: ...
user877329's user avatar
2 votes
2 answers
389 views

Optimizing a recursive path finding algorithm

On input i get width and height of matrix, string of text and another string of finalText I want to reach. The characters of the first string are assigned to matrix. My goal is to find shortest way to ...
Levyi's user avatar
  • 21
5 votes
0 answers
166 views

Dijkstra's algorithm in Perl

I have this Perl module project. My implementation of the Dijkstra's algorithm follows: ...
coderodde's user avatar
  • 28.4k
6 votes
3 answers
498 views

The shortest path between airports

Airlines need to provide their customers with flights to every corner, so they need an app that allows them to do so. The customer must be able to transfer when there is no direct connection. The ...
KermitTheFrog's user avatar
3 votes
1 answer
165 views

Traditional vs. bidirectional Dijkstra's algorithm in C

I have this CLion project on GitHub. It constructs a directed, weighted graph consisting of 100 thousand nodes and 500 thousand directed arcs, picks two random nodes, and computes the shortest paths ...
coderodde's user avatar
  • 28.4k
2 votes
1 answer
107 views

Priority Queue for D* Lite

So, I needed a priority queue for D* lite and I wanted to know whether this is an acceptable implementation or not. ...
a a's user avatar
  • 157
4 votes
1 answer
357 views

Searching for a performance bug in a C++20 pathfinding algorithm (NBA*) - follow up

I have followed some advice in the previous iteration, yet even the current version is too slow compared to the Java implementation of the same algorithm. (C++ version with ...
coderodde's user avatar
  • 28.4k
4 votes
1 answer
164 views

Searching for a performance bug in a C++20 pathfinding algorithm (NBA*)

(See the next iteration.) I have this pathfinding algorithm: DirectedGraph.hpp ...
coderodde's user avatar
  • 28.4k
1 vote
1 answer
109 views

Pathfinders.hpp - Dijkstra's algorithm

I have this Visual Studio 2022 project, in which I compared the performance of 4 point-to-point shortest path algorithms. This one presents the Dijkstra's algorithm: ...
coderodde's user avatar
  • 28.4k
1 vote
0 answers
78 views

My code generates a path through a grid - How can I simplfy it in terms of list, dictionary's, stacks and queues?

This code works but is cluttered and I think could be improved in terms of how it is implemented. Basically my code works - what it does is from the start location, it chooses a random direction and ...
Munkybunky's user avatar
2 votes
2 answers
460 views

Graph Implementation with Dijkstra's Algorithm

Graph Interface: ...
GodLike's user avatar
  • 51
4 votes
3 answers
429 views

Improving generic A* algorithm performance

Here is my A* algorithm. I tried hard to implement it generically, but come up only with one idea to use lambdas for heuristic and next nodes (neighbours / successors) functions. I know that using ...
David's user avatar
  • 51
2 votes
1 answer
110 views

Shortest route algo terribly slow

First post. I posted this on stack as well but somebody suggested I post it here too/instead. I wrote a shortest-path script for a Unity game project, and while it works, it gets so slow when applied ...
Colin's user avatar
  • 21
4 votes
3 answers
619 views

Compute shortest path in undirected graph

In a recent coding interview I was asked to write a program which takes as input two text lines: The first one represents a graph, formatted as a sequence of undirected edges like ...
InfiniteSnow's user avatar
1 vote
1 answer
366 views

Google Foobar challenge optimization

I am trying to solve Google Foobar challenge prepare-the-bunnies-escape using my own approach, instead of BFS. I attempt to solve two ends of the maze and try to ...
ScriptKidd's user avatar
2 votes
0 answers
112 views

AStar Implementation and Efficiency

This is my implementation of an AStar-like algorithm for maze solving. A quick summary of the problem I am trying to solve with my algorithm might be: A simple binary maze is given to you to solve, ...
ZeroMaxinumXZ's user avatar
2 votes
0 answers
64 views

Dijkstra from scratch

I implemented the Dijkstra algorithm from scrath and wonder if I can save some code? The whole algorithm is here. n is the number of nodes, and m the number of edges. 1 ≤ 𝑛 ≤ 10^4, 0 ≤ 𝑚 ≤ 10^5, 𝑢 ...
Lerner Zhang's user avatar
2 votes
1 answer
795 views

How can I speed up my IDA* algorithm for N-puzzle?

I'm trying to solve the N-Puzzle problem using IDA* algorithm with a Manhattan heuristic. I already implemented the algorithm from the pseudocode in this Wikipedia page (link). Here's my code so far : ...
cuzureau's user avatar
  • 191
4 votes
1 answer
514 views

A* Pathfinding Algorithm

I have programmed a A* Pathfinding algorithm in the Console. I would now like to know if there are any things that I could do to improve the time it takes, to find a path. Right now it takes around ...
Pablu's user avatar
  • 49
8 votes
3 answers
2k views

A* (shortest path) with the ability to remove up to one wall

Problem You are given an HxW matrix. Each element is either 0 (passable space) or 1 (wall). Given that you can remove one wall, find the shortest path from [0,0] (start) to [width-1, height-1] (end). ...
Martin's user avatar
  • 183
4 votes
1 answer
78 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 ...
Mert's user avatar
  • 49
10 votes
2 answers
4k 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 ...
O.B.'s user avatar
  • 103
6 votes
1 answer
1k 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 ...
V_head's user avatar
  • 525
5 votes
1 answer
190 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 (...
cajomar's user avatar
  • 161
6 votes
2 answers
777 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 ...
Xamtos's user avatar
  • 370
4 votes
2 answers
303 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 ...
inappropriateCode's user avatar
3 votes
1 answer
102 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 ...
inappropriateCode's user avatar
4 votes
2 answers
618 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 ...
Rebecca's user avatar
  • 41
2 votes
1 answer
370 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. ...
Ashish Pawar's user avatar
1 vote
0 answers
377 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 ...
user141240's user avatar
5 votes
2 answers
104 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 ...
Ian Taylor's user avatar
1 vote
0 answers
104 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 ...
thethiny's user avatar
  • 111
3 votes
2 answers
227 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 ...
cpplover's user avatar
  • 354
4 votes
1 answer
187 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 ...
Urbs's user avatar
  • 61
4 votes
1 answer
59 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 - ...
James Robinson's user avatar
4 votes
2 answers
999 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 ...
Balog Szilárd's user avatar
10 votes
2 answers
1k 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 ...
alec's user avatar
  • 109
2 votes
2 answers
300 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 ...
DragonGamer's user avatar
3 votes
1 answer
378 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. ...
user1747281's user avatar
7 votes
2 answers
3k 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 ...
Dave's user avatar
  • 753
8 votes
1 answer
2k views

Speeding up Dijkstra's algorithm

I have Dijkstra's algorithm: ...
Alexey's user avatar
  • 183
7 votes
2 answers
6k 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 ...
Dave's user avatar
  • 753
2 votes
0 answers
227 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 ...
Failware's user avatar

1
2 3 4 5