Questions tagged [a-star]
A* is a graph shortest-path algorithm that uses a heuristic function to speed up the search
71 questions
10
votes
2
answers
4k
views
A* algorithm implementation in modern C++
I've written the A* search algorithm in C++. My goal is primarily writing concise and understandable code, while making use of some new features of modern C++ (where appropriate) and having generally ...
2
votes
2
answers
140
views
0
votes
0
answers
163
views
A-star pathfinding algorithm to route through a raster maze
I have a problem that needs path finding to solve. It is a vector of ints; 1 for passable terrain and 0 for non-passable. My implementation is not fast enough for the test. How could I make it faster?
...
4
votes
1
answer
361
views
Searching for a performance bug in a C++20 pathfinding algorithm (NBA*) - follow up
I have followed some advice in the previous iteration, yet even the current version is too slow compared to the Java implementation of the same algorithm. (C++ version with ...
- 29.8k
4
votes
3
answers
438
views
Improving generic A* algorithm performance
Here is my A* algorithm. I tried hard to implement it generically, but come up only with one idea to use lambdas for heuristic and next nodes (neighbours / successors) functions. I know that using ...
- 51
2
votes
1
answer
808
views
How can I speed up my IDA* algorithm for N-puzzle?
I'm trying to solve the N-Puzzle problem using IDA* algorithm with a Manhattan heuristic. I already implemented the algorithm from the pseudocode in this Wikipedia page (link).
Here's my code so far :
...
- 181
4
votes
1
answer
707
views
A-star pathfinding algorithm
I'm working on a school project where I need to implement the pathfinding algorithm. The requirements are that it needs to find the path in at most a few seconds and ideally in less than 1 second. I'...
- 41
8
votes
3
answers
2k
views
A* (shortest path) with the ability to remove up to one wall
Problem
You are given an HxW matrix. Each element is either 0 (passable space) or 1 (wall).
Given that you can remove one wall, find the shortest path from [0,0] (start)
to [width-1, height-1] (end).
...
- 183
4
votes
2
answers
249
views
Solving 15Puzzle with Julia
Asking here instead of SO as suggested.
I'm trying to use Julia to solve the common tile game 15 Puzzle using Julia using A* algorithm. I am quite new to the language and my style may seem very C like....
- 53
6
votes
1
answer
1k
views
Python: Astar algorithm implementation
I have implemented Astar algorithm for a problem on an online judge relating to maze given start and end positions along with a grid representing the maze. I output the length of the path along with ...
- 535
5
votes
1
answer
197
views
A* and ALT pathfinding in C tips
I adding some pathfinding to a game I'm working on. It primarily used A* with as suggested in the pathfinding articles at reb blob games.
It works, but isn't very fast.
It is a square grid map that (...
- 161
4
votes
2
answers
628
views
I wrote my first pathfinding algorithm
I'm currently writing a small game in Lua, using the Love2d framework. I guess I'm doing it as a practice of sorts, but it did give me the opportunity to write my first pathfinding algorithm. I wrote ...
- 41
5
votes
2
answers
105
views
Performance Enhancement of A Star Path Finder algorithm with 1024 multidimentional array
I have the below code for a A* pathfinder, however it is taking upwards of 10 minutes to find a solution using a simple 1024 x 1024 array.
I had to comment out ...
- 51
4
votes
1
answer
192
views
A* pathfinding for integer Vectors
This class is for calculating the shortest path in a 2D World (without minding obstacles).
I'm using the A* algorithm and 2D Vectors (from the SFML Framework).
It is working but takes (a lot of) time ...
- 61
2
votes
2
answers
302
views
A-Star for 2D Graph (not grid)
This is my A-Star implementation for a 2D space of nodes but allowing to specifically set connections between nodes because my usecase does not have points tied to a grid (however for clarification ...
- 145
8
votes
2
answers
9k
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 :
...
- 145
33
votes
3
answers
9k
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 ...
- 511
3
votes
1
answer
2k
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 ...
- 585
4
votes
2
answers
2k
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 ...
- 2,815
3
votes
1
answer
721
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 ...
- 43
3
votes
1
answer
572
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 ...
- 373
3
votes
1
answer
299
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 ...
- 141
3
votes
2
answers
606
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 ...
- 97
3
votes
3
answers
2k
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 ...
- 97
3
votes
1
answer
770
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 (...
- 539
5
votes
1
answer
409
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)?
...
- 153
4
votes
1
answer
594
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 ...
- 43
5
votes
2
answers
5k
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 ...
- 51
5
votes
1
answer
350
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 ...
- 153
1
vote
0
answers
485
views
java - A* search algorithm
I'm having trouble with my homework implementing A* search algorithm in java, I'm given the graph, origin and destination, I had to follow some specific tasks in the homework so the code might be a ...
- 11
3
votes
2
answers
1k
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 ...
- 133
4
votes
0
answers
215
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 ...
- 161
4
votes
2
answers
4k
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 ...
- 41
2
votes
1
answer
16k
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:
...
- 131
8
votes
1
answer
826
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 ...
- 83
5
votes
1
answer
5k
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 ...
- 163
7
votes
3
answers
1k
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 ...
- 171
4
votes
2
answers
1k
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 ...
1
vote
2
answers
362
views
A* Algorithm implementation
This is an implementation of A* algorithm, that I will use in my game.
Navigation.hpp
...
- 305
2
votes
1
answer
87
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 ...
- 123
7
votes
2
answers
170
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 a ...
- 263
4
votes
1
answer
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 =...
- 181
4
votes
1
answer
2k
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
1
answer
446
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 ...
- 329
2
votes
1
answer
514
views
A* path finding getting the node neighbors
Is there any way I can minimise this code.The code will get the neighbours of the current node and point the arrow to the current node
...
- 147
7
votes
0
answers
546
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 ...
user73941
3
votes
0
answers
117
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 ...
- 786
3
votes
1
answer
333
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 ...
- 786
10
votes
1
answer
270
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.
...
- 103
-4
votes
1
answer
110
views
