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.

learn more… | top users | synonyms

2
votes
0answers
23 views

Djkistra shortest path implementation for adjacency list represented graph

Please review the implementation of Djkistra algorithms. Points on which I have doubt: My Graph doesn't have any ID for nodes. Nodes are accessed based on their ...
8
votes
3answers
194 views

Finding shortest paths in directed graphs

I have very little experience in programming with C++ and the following small "program" is the 2nd one I have ever written in that language. I am most interested in comments regarding naming ...
-1
votes
3answers
101 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 ...
5
votes
2answers
259 views

Tremaux Algorithm

I am trying to implement Tremaux Algorithm for a 2D maze. So far the robot works well however I have some problems with retraceStep(). I'm not asking how to ...
2
votes
1answer
83 views

Finding the shortest path in a graph

Could you please advise on the code and its design? Is there any way I can apply object oriented principles to make the design robust yet flexible? ...
5
votes
2answers
116 views

More optimized approach of Dijkstra's algorithm

I need a graph-search algorithm that is enough in our application of robot navigation and I chose Dijkstra's algorithm. We are given the gridmap which contains free, occupied and unknown cells where ...
10
votes
2answers
182 views

Contest code for a maze problem

I would like to ask your comments on my contest code for the following problem: We're going to have a slightly more logical puzzle today. We're going to write a program that will find a path through ...
2
votes
1answer
41 views

Is this Python pathfinder efficient enough?

I'd like to see if my code follows common practice, or is already efficient or fast enough. ...
4
votes
1answer
108 views

Finding Shortest Path

Working on Functionally Solving Problems from Learn You a Haskell, I worked on the "Heahtrow to London" shortest path problem. I'm working on a reduced set of this problem in order to solve a simple ...
10
votes
3answers
108 views

Optimization of aStar in Java

I'm currently looking to optimize my aStar algorithm as my last run through took roughly a minute to generate one path. I've never had to optimize before as I've never run into performance issues, so ...
2
votes
1answer
71 views

Retaining depth information and recursive traversals

I have been using the pattern below for some time and it has worked well, but more than once I have almost bled my brain out of my ear trying to keep track of: the recursion depth the recursion path ...
6
votes
1answer
208 views

Escaping the prison - finding the shortest way

I have given an assignment where I have to escape a labyrinth. The goal is to find the shortest way. I have done some research and there seem to be two strategies to solve the problem: the Depth-first ...
10
votes
2answers
2k views

Recursive maze solver

Up for review today is some C++11 code to recursively search a maze for a path to a specified goal. This one shows dead-ends it explored on the way to finding the solution. ...
2
votes
1answer
234 views

Why does this Python maze-solver NOT get stuck? [closed]

I wrote the following Python program, which reads text files as mazes and displays the solution with a trail of Xs. The files must have an S for the start and an E for the end, and the walls must be ...
3
votes
2answers
262 views

Recursive uniform cost search that needs to be optimized

I have this uniform cost search that I created to solve Project Euler Questions 18 and 67. It takes the numbers in the txt file, places them into a two dimensional list, and then traverses them in a ...
12
votes
8answers
7k views

Is my AI solution to Untrusted Game considered logical or “ethical”?

I am applying to a university to study Computational Linguistics, and as I read, it would be recommended to have a background in Artificial Intelligence. The Admission board asked me to prepare a ...
8
votes
5answers
1k views

Efficient pathfinding without heuristics?

Part of my program is a variable-sized set of Star Systems randomly linked by Warp Points. I have an A* algorithm working rather well in the grid, but the random warp point links mean that even though ...
8
votes
2answers
168 views

Finding path in Maze

I recently gave an interview and was asked the following question. I posted this here Finding path in Maze also, and someone suggested I should try Code Review. So here it goes. A maze is a group of ...
7
votes
3answers
696 views

Shortest path algorithm is too slow [closed]

I am solving one problem with shortest path algorithm, but it is too slow. The problem is that I have N points and these can be connected only if the distance between them is smaller or equal than ...
4
votes
1answer
140 views

Tilt maze solution

If one does not know tilt maze then the game looks like this. Basically one can travel in 4 directions North, East, South and West, but this travel's endpoint is the furthest non-obstructed block. If ...
10
votes
2answers
665 views

Find a path through a maze

This maze has multiple entry points, and quite obviously multiple exits. The entry or exit is not provided at input. Of the multiple sources and destinations, any single path from any source to any ...
7
votes
6answers
1k views

Getting the shortest sequence to reach a number

I want to get the shortest sequence to reach a number. Rules: A[0] is always 1 Either A[i] = A[i-1]*2 or ...
11
votes
3answers
1k 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, ...
3
votes
2answers
315 views

Time Limit Exceeded in BFS maze solver

Here's a problem that I tried solving: Lakshagraha was a house built of lacquer, made by the Kauravas to kill the Pandavas. The Kauravas wanted to burn the house down when the Pandavas were ...
10
votes
3answers
8k views

A* search algorithm

NodeData stores all information of the node needed by the AStar algorithm. This information includes the value of ...
4
votes
2answers
1k views

Count possible paths through a maze

You have to find a path through which the rat move from the starting position (0,0) to the final position where cheese is (n,n). List the total no of possible paths which the rat can take to ...
3
votes
1answer
214 views

Path Planning - Greedy Best First Search

I'm working on a path planning algorithm that will be converted to RobotC. I'm trying to optimize it so that it uses the least amount of memory, as the robot it will be implemented on has supposedly ...
4
votes
1answer
537 views

Optimizing this maze-solver

I've written C# code for solving a maze problem. It works, but I want to optimize it so that it could give me all paths. To solve the maze, I walk on the zeros and assumed that the final is reaching ...
4
votes
3answers
282 views

Maze problem cleanup and optimization

Maze, assumption - single point of entry and a single point of exit. Also directions to travel in maze are North South East West. Request for optimization and code cleanup. ...
2
votes
2answers
2k views

Finding a route in maze matrix

Maze puzzle A 1 in input matrix means "allowed"; 0 means "blocked". Given such a matrix, find the route from the 1st quadrant to the last (n-1, n-1). I would like to get some feedback to ...
7
votes
2answers
259 views

How can I improve my A* Pathfinding code? (again!)

Done this already, but looking to improve it even more. Nearly time to hand this project in, and I want it to be as close to perfect as possible. So, any issue (No matter how small) - Let me know. If ...
6
votes
2answers
115 views

A* path finding algorithm for a red-black tree

So far I've implemented a way to add to my RedBlackTree (will be used with A* pathfinding - hence the F value). I'm not entirely sure how to improve it further. I ...
5
votes
2answers
1k views

How can I improve upon my A* Pathfinding code?

How can I make it faster, more efficient, and simpler? Are there any obvious mistakes I've made, or things which will make my code "fancier"? It's my first time working with any form of pathfinding, ...
3
votes
3answers
2k 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 ...
6
votes
1answer
128 views
3
votes
1answer
346 views

How can I make my A* algorithm faster?

This is a slightly specialised A* algorithm, basically it allows you to search to and from disabled nodes. It's for a game and we the entities spawn in houses and go into them. The rest of the search ...
4
votes
4answers
743 views

Javascript A* pathfinding function for tile-based game optimisation

Below are the bunch of functions which I wrote to determine paths between give coordinates of a square tile-based game. It permits paths between tiles in 4 directions (i.e. not 8 directions/diagonal ...
4
votes
1answer
652 views

Path sum - Dijkstra's algorithm in F#

I'm learning F# and I've decided to solve Project Euler's Problem #81 with Dijkstra's algorithm. In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only ...
8
votes
0answers
818 views

A* implementation [closed]

I've implemented A* according to the pseudo-code on Wikipedia. I'm going to worry about optimizing it later, but for now, I'd really like to know if the code is correct. ...
10
votes
4answers
847 views

Maze generation

I have been working on a maze generator in C++ in an effort to learn the language and brush up on some long lost knowledge. I want to ensure that I am using best practices, and really doing things the ...
8
votes
1answer
866 views

Path finding function

Could this be made more efficient, and/or simpler? It's a path-finding function. It seems to work, but do you see any potential cases where it could fail? ...