# Tag Info

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 ...
• 5,976
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. ...

### A* pathfinding algorithm too slow

Avoid recursion if the iterative solution is easily available. Rewrite recursion in a tail-recursive fashion: ...
• 56.2k
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: ...
• 97.3k
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 ...
• 9,464

### 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 ...
• 54k

### 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 "...
• 9,464

### 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 ...
• 2,057

### 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 ...
• 54k
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: ...
• 16.6k
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 ...
• 9,464

### 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 ...
• 12.8k

### 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 ...
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 ...
• 19.1k

### 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 ...
• 5,580

### 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 ...
• 16.6k

### A* algorithm as simple as possible

def is_invalid_position(maze, node): Why node? The only things used by this method are maze...
• 24.1k

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 ...
• 16.3k
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 ...
• 11.6k
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 ...
• 9,146

### 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 ...
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 '...
• 7,431
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 ...
• 16.3k
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 '...
• 7,431
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 ...
• 54k

### 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: ...
• 74.4k
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 ...
• 11.6k
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 ...
• 11.6k