Hot answers tagged

140 votes
Accepted

A* pathfinding algorithm too slow

There is some reasonable general algorithmic and python-specific advice here. The lesson that needs to precede everything is, until you know where you're spending your time, you can't work out how ...
Josiah's user avatar
  • 5,976
29 votes
Accepted

Optimizing an A* algorithm

Without looking too closely at your actual algorithm, I can tell you're using the wrong data-structures. closedSet should to be a set. ...
BlueRaja - Danny Pflughoeft's user avatar
12 votes

A* pathfinding algorithm too slow

Avoid recursion if the iterative solution is easily available. Rewrite recursion in a tail-recursive fashion: ...
vnp's user avatar
  • 56.2k
9 votes
Accepted

A* Go application

Bug Your code clearly states: Src: 0, 0 Dst: 0, 5 Excpeted answer: {(0,0), (1,1), (2,2), (2,3), (2,4), (1,5), (0,5)} But, when I run your code, I get: ...
rolfl's user avatar
  • 97.3k
9 votes
Accepted

Implementation of A* algorithm in C++

Euclidean distance is used to calcualte the cost from current node to goal The code implements Manhattan distance, so the comment is wrong, or perhaps the code is wrong, but in any case it doesn't ...
harold's user avatar
  • 9,464
9 votes

A* algorithm implementation in modern C++

Missing and redundant const Make sure that all pointer and reference parameters that point to data that should not be modified are passed as ...
G. Sliepen's user avatar
8 votes

A* algorithm implementation in modern C++

As I understand your code, a new node is pushed for every unvisited neighbour of the node that is visited. A result of that is that the queue will contain, in many cases, duplicate nodes, or "...
harold's user avatar
  • 9,464
6 votes

A* search in MATLAB

You say getNeighboursByIndx takes 50% of the total time. That means that you should try to reduce either: The number of calls to ...
Stewie Griffin's user avatar
6 votes

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

Don't put implementation in header files You moved all of your code into header files. That's not what they are for. It is better to have only the declarations of the classes and functions in the .h ...
G. Sliepen's user avatar
6 votes
Accepted

A* Pathfinding for a Game

Calling PriorityQueue.contains is O(n) in the size of the priority queue and this ruins your performance. For example here: ...
Emily L.'s user avatar
  • 16.6k
6 votes
Accepted

A* (shortest path) with the ability to remove up to one wall

The high level approach What would be a good way of implementing the wall logic to be within the A* algorithm? I've tried to simply add a canRemove boolean to the Cell object (which is holding the ...
harold's user avatar
  • 9,464
5 votes

Optimizing an A* algorithm

openSet is sorted at the start of each while loop and the sorted list thrown away (if I read that selection syntax right). This is a cost of O(n log n) on each ...
ratchet freak's user avatar
5 votes

Algorithm to find a path

In terms of performance, by far your biggest gain will be in using the correct data-structures. open_list is supposed to be a priority queue and ...
BlueRaja - Danny Pflughoeft's user avatar
5 votes
Accepted

Algorithm to find a path

Currently, you are doing far too many allocations, and for way too much space. Remember that dynamic allocation is quite costly, even more so in C than in Java, at least for smaller structures. What ...
Deduplicator's user avatar
  • 19.1k
5 votes

Moving game objects along an A* Path

You can improve the performance by using appropriate data structures. You can obtain the closest node using a PriorityQueue. You can use a ...
kraskevich's user avatar
  • 5,580
5 votes

A* search on 4x4 sliding tile puzzle scales poorly

You're doing the same mistake that everyone who posts that their A* is slow is doing. You're using the wrong data structure for your open and closed structure. The closed should be a set, usually ...
Emily L.'s user avatar
  • 16.6k
5 votes

A* algorithm as simple as possible

def is_invalid_position(maze, node): Why node? The only things used by this method are maze...
Peter Taylor's user avatar
  • 24.1k
5 votes

Implementation of A* algorithm in C++

Just off the cuff, before I fully code review this, I would tell you: 1) There are not enough comments. You add comments like this: ...
Gabriel Rohweder's user avatar
5 votes
Accepted

Python: Astar algorithm implementation

self.start, self.grid, self.height, self.width = start, grid, height, width I would not put these all on the same line like that. I think it would be much easier ...
Carcigenicate's user avatar
5 votes
Accepted

Searching for a performance bug in a C++20 pathfinding algorithm (NBA*) - follow up

Your main issue appears to be in checkTerminalNodes, which copies the entire graph. It should be passed by const& instead of ...
user673679's user avatar
  • 11.6k
4 votes
Accepted

Game of 15 - A* search

I'll focus on the readability part of your code: Don't import modules you're not using. (import itertools) Don't import modules in the middle of your code. All the ...
Grajdeanu Alex's user avatar
4 votes

Moving game objects along an A* Path

Pathfinding is a complex topic and there's a lot of information about it in the web. I highly recommend to invest some time into reading about it. If you have a high number of objects chasing a low ...
Arnold Braunschweiger's user avatar
4 votes
Accepted

Shortest path to transform one word into another

Ran out of space in one comment, so figured I'd better write an answer... Overall, the code is pretty readable and easy to follow. Performance is an obvious concern, however, and there are a few '...
VisualMelon's user avatar
  • 7,431
4 votes
Accepted

A* in Clojure - trickier than I expected

I'm not going to be able to do a very thorough review. The code doesn't have anything outright wrong with it, and I'll admit, I've never been able to implement a decent A* implementation. It's just ...
Carcigenicate's user avatar
4 votes
Accepted

Latitude/Longitude graph optimised A* Algorithm

Performance I won't say much about the algorithm, but the profiler has pointed you in the right direction: what you need is a Priority Queue. A Priority Queue will enable you to keep track of the '...
VisualMelon's user avatar
  • 7,431
4 votes
Accepted

C++ - Astar search algorithm using user defined class

A std::vector<std::vector<int>> is an inefficient way to store a 2-dimensional array. Unfortunately, there is nothing in the standard C++ library that ...
G. Sliepen's user avatar
4 votes

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

Platform-dependent code There's no need to bring in <Windows.h> - with a couple of small changes, this can be portable C++, accessible to everyone: ...
Toby Speight's user avatar
  • 74.4k
4 votes
Accepted

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

Bugs: A lot of memory is allocated (foo = new Container) and never deallocated (delete foo). N-puzzle implementations usually ...
user673679's user avatar
  • 11.6k
4 votes
Accepted

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

Good job refactoring. It looks much neater without the globals / Manager class. Good effort with cleaning up allocated memory, but we can do better (see below). The ...
user673679's user avatar
  • 11.6k
4 votes
Accepted

N-puzzle solver using A* search

Advice 1: l_moves The name l_moves is ain't good at all. Consider numberOfMoves. Since it ...
coderodde's user avatar
  • 27.5k

Only top scored, non community-wiki answers of a minimum length are eligible