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.

26 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
36 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 ...
4
votes
0answers
89 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 ...
3
votes
0answers
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: ...
3
votes
0answers
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. ...
3
votes
0answers
61 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 ...
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 ...
3
votes
0answers
118 views

Codingame: Great Escape bot in Ruby - Follow-up

This is a follow-up to Codingame: Great Escape bot in Ruby. As mentioned there, my first reasonably sized Ruby project is a bot for CodinGame's Great Escape contest (here is a sample gameplay video). ...
3
votes
0answers
101 views

F# implementation of the A* algorithm round 2

This is my second attempt at implementing the A* algorithm using F#, the first one is here. What I changed: I removed the Node class and added two records named ...
3
votes
0answers
2k views

Brute force shortest path in Java

I had to ask myself a couple years ago: before Edsger Dijkstra invented his famous shortest path algorithm, how brute force approach would seem. Below is my version. It's super slow, but I find it ...
3
votes
0answers
381 views

Golang A* Pathfinder

This is a generalized A* pathfinder in Go. I am new to the language and am eager for advice about best practices. In particular, I am not sure if the type assertion I make in ...
2
votes
0answers
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: ...
2
votes
0answers
56 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, ...
2
votes
0answers
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, ...
2
votes
0answers
44 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 ...
2
votes
0answers
111 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 ...
2
votes
0answers
504 views

Routing simulation (Distance vector)

I am trying to write simulation for routing algorithm by distance vector. I will explain my class and how it works a bit, and then, introduce three main issues I encouter. Important to mention that ...
2
votes
0answers
1k views

Dijkstra's single source shortest path algorithm (with Fibonacci heap)

I implemented a generic Dijkstra algorithm. It's lazy since the vertices with their final distances are request on demand. I used the Fibonacci Heap from this question with a few changes (added a copy ...
2
votes
0answers
762 views

A simple graph walk interception algorithm in Java

I have that girl whose graph walk I want to intercept, but because I am not good at running algorithms in my head, I had to program my computer to do that for me. I would not consider the problem to ...
2
votes
0answers
299 views

A* search algorithm in Clojure

Cost of nodes are represented by a matrix (called world), heuristic cost estimate/g score/f score are all represented in matrices. The world and its size are ...
2
votes
0answers
131 views

AI for depth-first walking in a maze, with variable depth look ahead search for dead ends and finish point

This code is a part of a little game I've started a week ago. It is too extensive to review at once, so I'm picking the most interesting and crucial parts. Start with the AI. It has public update ...
1
vote
0answers
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 ...
1
vote
0answers
145 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 ...
1
vote
0answers
44 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 ...
1
vote
0answers
81 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: ...
1
vote
0answers
61 views

Thread pool based unweighted path finder in Java for graphs with slow expansion operator

Introduction Given a directed unweighted graph, the objective of this library is to find a shortest path from a given source node to a given target node. Clearly, one candidate algorithm to find ...
1
vote
0answers
24 views

Wikipath stack in Java - Part II/IV - The implicit Wikipedia article graph

This question is the continuation of the Wikipath stack series: the two classes that - given a Wikipedia article \$A\$ - return the lists of neighbour articles. The forward node expander return the ...