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

10
votes
2answers
103 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
39 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
76 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
91 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
60 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
165 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
602 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
151 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
225 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
889 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
149 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
668 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
111 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
468 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 ...
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
253 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
2answers
5k 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
938 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
180 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
454 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 ...
3
votes
3answers
250 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
231 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
106 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
908 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
1k 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 ...
5
votes
1answer
121 views
3
votes
1answer
336 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
724 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
628 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
796 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. ...
8
votes
1answer
827 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? ...