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
1answer
96 views

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

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
101 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
6answers
5k 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 ...
7
votes
5answers
720 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
109 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
616 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
68 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
246 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 ...
10
votes
3answers
609 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
148 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 ...
6
votes
1answer
783 views

A* search algorithm

A* search algorithm. Looking for reviews on optimization, accuracy and best practices. ...
4
votes
2answers
337 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
116 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 ...
1
vote
0answers
291 views

How to optimize 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
228 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
877 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
184 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 ...
5
votes
2answers
604 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. Code optimization

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 ...
3
votes
1answer
276 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
591 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
553 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
747 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
684 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? ...