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.
10
votes
3answers
67 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 ...
8
votes
5answers
818 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 ...
2
votes
1answer
51 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
...
7
votes
2answers
3k views
A* search algorithm
A* search algorithm. Looking for reviews on optimization, accuracy and best practices.
...
5
votes
1answer
120 views
6
votes
1answer
129 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
306 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.
...
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 ...
4
votes
2answers
618 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 ...
12
votes
8answers
6k 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 ...
2
votes
1answer
121 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
121 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 ...
10
votes
3answers
764 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, ...
4
votes
1answer
592 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
1answer
761 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?
...
7
votes
2answers
211 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 ...
8
votes
2answers
130 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 ...
3
votes
1answer
323 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 ...
7
votes
3answers
644 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 ...
10
votes
2answers
319 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 ...
4
votes
1answer
84 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 ...
3
votes
2answers
208 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 ...
2
votes
2answers
1k 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 ...
3
votes
3answers
233 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.
...
1
vote
0answers
357 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
1answer
154 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 ...
5
votes
2answers
753 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, ...
4
votes
4answers
675 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 ...
8
votes
0answers
769 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.
...
