The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [a-star]

A* is a graph shortest-path algorithm that uses a heuristic function to speed up the search

Filter by
Sorted by
Tagged with
32
votes
3answers
7k views

A* pathfinding algorithm too slow

I'm trying to make a pathfinding algorithm for my project. I need it for a simulation and I need it to be fast!!! I watched a few videos explaining the algorithm online and came up with the code ...
14
votes
3answers
3k views

Optimizing an A* algorithm

I am currently using an implementation of the A* algorithm described here. Currently, when I run my algorithm, my IDE lags horribly and the .exe generated also lags terribly. Using the CPU analyzer, ...
14
votes
2answers
2k views

A* search in MATLAB

I have implemented A* search in MATLAB, but I am looking for ways to increase the speed and optimize it. I have tried using a priority queue but I found it doesn't work that well, so I am using a ...
13
votes
1answer
7k views

Solving 15 puzzle

I'm trying to solve 15 puzzle using A* algorithm, but something really bad goes on in my get_solution() function that ruins performance. I guess there is a too much ...
12
votes
1answer
343 views

A* Go application

I've written a generic implementation of the A* algorithm as a first Go program, since I had implemented that both in C and in Python before and Go reminds me a bit of both. I'm looking for general ...
10
votes
1answer
148 views

Game of 15 - A* search

I would be really thankful for review of this homework. I'm trying to write better code in terms of readability and design patterns. This program solves the classic 15 slider puzzle with A* search. ...
10
votes
2answers
254 views

Typesetting A* in LaTeX using algorithm2e

(See the next iteration.) The result looks like and my code is: ...
8
votes
2answers
2k views

Implementation of A* algorithm in C++

I have implemented the A-Star path finding algorithm for a 2D grid. The function returns a list of positions of an acceptable path. main.cpp : ...
7
votes
3answers
877 views

Moving game objects along an A* Path

I am having a game with a lot of GameBodyObjects and some of them are moving, some of them are not. When I calculate A* for the moving objects it gets really slow ...
7
votes
2answers
131 views

Algorithm to find a path

I have implemented A* in C, and was wondering about what I could do to improve it. My main concerns are readability, usability and last but not least performance. My NodeList is an attempt at making ...
7
votes
3answers
6k views

8puzzle solver using A*

That's gonna take long. This program solves 8 puzzle game (mini version of 15 puzzle) using A* algorithm. Program consists of 2 parts: Board.java - which serves ...
7
votes
1answer
525 views

Shortest path to transform one word into another

I submitted the following code for a job application, and was rejected. They gave no feedback. Would appreciate any comments on the approach I took, and coding style. This is the question: Given ...
6
votes
1answer
301 views

A* algorithm in C# for use in a game

I recently started up again on a 2D game engine I have been working on over the last couple of years. I managed to implement a version of the a* algorithm that seems to work fine for my game, but it ...
6
votes
1answer
372 views

A* Generic Implementation in Swift

My first Code Review post. I'm up to a generic implementation of the A* search algorithm in Swift (for now, it's a single goal implementation). Here's what's been coded so far: ...
6
votes
0answers
325 views

A* Algorithm in F#

Inspired by this post I looked up A* on wikipedia and went on with my own implementation as seen below where I try to mimic the pseudocode on Wikipedia but in a recursive manner. I would like any ...
5
votes
1answer
2k views

A* search algorithm: open set and heap

I'm working on an A* search algorithm implemention and this is what I came up with for the open list: ...
5
votes
1answer
128 views

Latitude/Longitude graph optimised A* Algorithm

Can anyone point me in the direction of a C# or pseudocode implementation of A* optimised for relatively sparsely connected graphs (average < 3 edges per node)? ...
5
votes
1answer
137 views

A* implementation is not running efficiently but gets correct result

I'm not entirely sure what code other people will need to see, if I miss something off that is important please leave me a comment and I will update it as soon as I possibly can. I have coded an A* ...
5
votes
2answers
1k views

C++ implementation of the A* pathfinding algorithm

A lot of the code I show here is simply setting the environment and doesn't really affect the algorithm itself, so please don't get scared away by the amount of code. The algorithm itself is showed at ...
5
votes
1answer
1k views

A* implementation

I wrote a little A* implementation by my own and would like to have some feedback ;) The code is in OOP way, thus we can use an other pathfinding algorithm easily. The "Base" is just the interface ...
5
votes
0answers
167 views

A* algorithm optimization and implementation

I am implementing the A* algorithm in Python and have successfully completed the task. It works and even spits out the coordinates from the start to the end. However, I am programming a bot for a ...
4
votes
2answers
2k views

My 15 puzzle solver is too slow

It takes my code over 700 seconds to solve simple puzzle: 2 7 11 5 13 0 9 4 14 1 8 6 10 3 12 15 My function ...
4
votes
2answers
369 views

A* algorithm as simple as possible

I'm a beginner when it comes to path finding, so I decided to write an as simple as possible (to me) A* algorithm to learn. I looked up on internet the general idea and found some pseudo-code that I ...
4
votes
1answer
151 views

A* in Clojure - trickier than I expected

While working through some coding puzzles to brush up on Clojure, I encountered the need to use A* on some search problems. I tried to implement it from first principles/memory and that didn't go ...
4
votes
2answers
718 views

Find shortest path using A*

I have this c++ program. It is about A* algorithm, but the way it is written, its very hard to be understood and very hard to read. How would you edit the code so it is more correct grammatically and ...
4
votes
2answers
3k views

New way of doing the A* Algorithm

I wrote a Python script for implementing an A* algorithm. Map, Start and Goal are given. The code works well as far as I tested it but I want to get feedback from the best out there too. So I am ...
4
votes
1answer
3k views

A* (A-Star) pathfinding algorithm with dynamic node generation in Python

I wrote code which implements the A* algorithm in Python. A* is a shortest path algorithm which resembles Dijkstra's Algorithm, but includes an estimator to guide the search. The pseudocode of both ...
4
votes
1answer
1k views

Python: AStar Pathfinder algorithm

Traverse through any binary array using the Manhattan distance by giving a start node location and an end node location. The neighbor() method gives the neighbors next to the x,y coordinates that are =...
4
votes
1answer
718 views

Using the A* algorithm to search a graph generated from a grid

Following on from my previous question, I finally got round to actually doing the A* search for the Graph<MapTile>. The changes to the code from the previous ...
4
votes
1answer
827 views

Slow 8/15-puzzle IDA*

I am trying to find the optimal solution for a given 15-puzzle. So far as I can tell, the algorithm works (on simple instances of 8-puzzle), but is extremely slow for complex starting states (order of ...
3
votes
3answers
791 views

N-puzzle solver using A* with Manhattan + Linear Conflict

I've been working on this solution for a couple days now. Finally managed to get it to work and I got it to where it solves about half of the time. The other half goes for so long that it eventually ...
3
votes
1answer
438 views

A* Pathfinding for a Game

I'm working on a game and I have developed A* path finding for certain enemies. But I think I have some optimization issues. If I put the player in an area that cannot be reached and put 3 or 4 ...
3
votes
1answer
128 views

A* search on 4x4 sliding tile puzzle scales poorly

I am trying to improve the time complexity of my A* search algorithm and I have tried approaching this from every which way I believe is possible. I believe I may be doing something fundamentally ...
3
votes
1answer
239 views

N-puzzle solver using A* search

I have written a Java program to solve a N-puzzle with A* search and manhattan distance. My program can solve every 8-puzzle I have tested under 1 second, but it can't solve a 15-puzzle after 30 ...
3
votes
2answers
439 views

C# A* Pathfinding implementation, focusing on reusability and efficiency

I wrote a C# A* pathfinding (Though, it's generic enough that it could be used for other search purposes) implementation. I started this when I found that existing implementations often didn't support ...
3
votes
1answer
125 views

Typesetting A* in LaTeX using algorithm2e - follow-up

(See the previous and initial iteration.) I have this second version of my LaTeX code. I made it less dry by removing the duplicate keyword definitions shared by the two algorithms being typeset. ...
3
votes
1answer
117 views

A-Star Search with 3D Universe

I am attempting to write up a program in Python that will find the shortest path between two nodes in 3D space. The actual domain is the EVE-Online Universe, which is composed of systems connected by ...
3
votes
1answer
201 views

C++ 8-Sliding Puzzle Solver is very slow

I have made a sliding puzzle solver which is currently for 8-puzzles only. It works too slowly even though it is based on an A* algorithm whose f-score is calculated on the basis of Manhattan Distance ...
3
votes
1answer
174 views

F# implementation of the A* algorithm

This is my first attempt at writing something useful in F# and in a functional way in general. I would appreciate if you could point out any issue, even details, as I'd like to put all the bad habits ...
3
votes
1answer
220 views

Optimisation of A* in C++

I'm working on an A* pathfinding algorithm to solve a programming problem, and part of the constraint is the runtime. I need to find a path in a 2D grid with blocked or non-blocked tiles. You can't ...
3
votes
1answer
461 views

A* Search with Array Lists

I implemented A* Search with Array Lists following the pseudocode here. I have been working with different algorithms on my own, and now, I am trying to optimize them so that I can run them with less ...
3
votes
1answer
8k views

8-Puzzle using A* and Manhattan Distance

I have developed this 8-puzzle solver using A* with manhattan distance. Appreciate if you can help/guide me regarding: 1. Improving the readability and optimization of the code. 2. I am using sort to ...
3
votes
1answer
121 views

Python A Star with fewest turns and shortest path variations

I had a lot of fun writing these. I haven't seen a version minimizing turns, so that was a neat challenge. Any suggestions are very welcome. Is there anything to gain by making more method variables ...
3
votes
1answer
4k views

A*, Uniform cost and Greedy Best first search implementations

I am writing the code for A*, Uniform cost search and Greedy best first search algorithms in Java. I have finished the code which is working fine but I have used a bit different design strategy while ...
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 ...
2
votes
2answers
226 views

Npuzzle solver using A* with Manhattan + Linear Conflict (Updated Code)

Here is the old thread that I started out with. The code I've got now is vastly different thanks to those two. What I have now functions fairly well and looks pretty good. I've managed to work it back ...
2
votes
1answer
97 views

C++ - Astar search algorithm using user defined class

The objective of the post is to improve design and improve command on C++. Given a map, start point and end point, the shortest path to end point from the start point has to be found out using Astar (...
2
votes
1answer
469 views

A* search algorithm: classes

So, this is a ton of code, but that's what I came up with for an efficient and extendable implementation of the A* search algorithm. The first four classes can be seen as interfaces to show the user ...
2
votes
1answer
7k views

A* implementation of 8 puzzle

I'm trying to implement 8 puzzle problem using A Star algorithm. The goal state is: 0 1 2 3 4 5 6 7 8 and the heuristic used is Manhattan distance. Here's the code: ...
2
votes
1answer
60 views

Generic A*-Algorithm without clone

I wrote a generic implementation of A* with the focus of not having to clone nodes or actions. Thanks to some very good advice I received on Stack Overflow, I have arrived at the following final ...