Your code really help me a lot but I have a question that in the SearchStep() method, why do you consider the closed list like the open list. In other word, I think when the successor is in the CLOSED list, we should ignore it directly, but you try " if node_successor is on the CLOSED list but the existing one is as good or better then discard this successor and continue ".

Hi,

I made some improvements on this project and if you want to use some of them I can provide it. I had to do some experiments to analyze a new heuristic algorithm and so I implemented two different methods, one to generate the next state provided another state, and another one to generate a random() state. To avoid the usage of unsolvable states, I´ve created a method to check if the state is solvable or not. As I need to put the algorithm to execute several times I introduced a second argument with the number of repetitions and put all this in a loop. There are some modifications about the heuristics but it is related to my own experiments, but I can explain them if you wish.

    // Fixed sizes for collections
    readonly int kPreallocatedNodes = 80000;
    readonly int kPreallocatedMapSearchNodes = 80000;

I fixed the number of this, it's still have an error of “FATAL - HexGrid has run out of preallocated MapSearchNodes”。 what's wrong of it?

I'm working on a game that uses A-star (A*) for path finding but I've come to a point where by I have some objects that are larger than a single grid square.

I'm running on a grid of 16_16px. wall segments are 16_16 and so make a single square impassable. Some of my baddies are 32*32 and so they need to check that a gap is at least 2 grid square wide in order to be able to pass throguh it.

I can't simply make the grid 32_32 as the design requires thin walls (at 16px) and there are a couple of smaller baddies that only take up a single 16_16 square.

How do I implement this mutli-resolution environment? Is A-star still the correct tool to use?

The algorithm opts for an irregular path when running in my project. This could be just me and the settings I've configured but the following is generated with an irregular path, which should've been a straight one -

^ denotes the path
. denotes unwalkable tiles

the code can be found here -
https://github.com/horizonxyz/horizon/blob/status/src/Tests/AStarTest.cpp

map data can be found here -
https://github.com/horizonxyz/horizon/blob/status/src/Tests/prontera.cpp

I made my own version of the node class and it wouldn't compile, so I tried to compile both example files and both give me this error:
h:\programming\c++\astar-algorithm-cpp-master\stlastar.h(60): error C2338: UserState must be derived from AStarState!
h:\programming\c++\astar-algorithm-cpp-master\8puzzle.cpp(569) : see reference to class template instantiation 'AStarSearch' being compiled with
[
UserState=PuzzleState
]

I didn't edit any of the files, is this a known issue?

Hi,

Thanks for the awesome code!

I have a question, this is the first A-Star I have ever implemented, and I'm getting these winding results
instead of a straight line - is this normal for A-Star?

https://i.imgur.com/g113sCK.png

note: entire map is initialized to a cost of 1

thanks again for any suggestions you might have

edit: with the entire map initialized to a cost of 0, I get this even stranger result : https://i.imgur.com/3UuJWLk.png

looking for it to be a straight line unless there are obstacles, any ideas?

For those not using C++ a C interface would be useful.

Hi there!
My program crashes when I am calling FreeSolutionNodes() without any preparation (on clear algorithm object). I noticed this function doesn't check m_Start for existence. Also it was not initialized in constructors, so the value is unpredictable. I added initialization with zero pointer and

if( !m_Start )
return;

lines in function body. Now that works. Can you check if this is good solution, and if it is so, place it in code?

Thank you.

Hi

The GoalDistanceEstimate numbers are not euclidean distance, nor the actual distance as per google. I understand you have taken directly from Norwis's AIMA, and I could not find any clue any where how they arrive at these values. Can you please check?

I recently always get this assertion failure.
I checked and seems the m_AllocateNodeCount fails with value -2
Do you have any suggestions? Thanks!

Update:
I think I have located where is the cause: I called FreeSolutionNodes() when I didn't get a solution...
This frees m_Start and m_Goal, with decreasing the m_AllocateNodeCount to -2.

But anyway m_Start/m_Goal is allocated by AllocateNode()
Shouldn't we free it? Thanks!

Is it possible to limit path steps to up, down, left and right without diagonal moves?

Is there an example of how to allow diagonal moves?

You should be careful about the memory alignment of the USER_TYPE

Using namespaces in headers is considered bad practice because they unconditionally and irreversibly pollute the global namespace of every consumer.

This leads to conflicts especially since the std namespace uses a lot of general terms that someone might want to use elsewhere, for example function and copy. The user in microsoft/STL#1881 was having issues with a library conflicting with the standard library specifically because of this line (the library is in the endian namespace while C++20 has an std::endian enum now):

The source .cpp files, however, can keep doing using namespace std since it won't affect any other files.

Why is this return 9 there?

int GetMap( int x, int y )
{
    if( x < 0 ||
         x >= MAP_WIDTH ||
         y < 0 ||
         y >= MAP_HEIGHT
         )
    {
        return 9;
    }
    return world_map[(y*MAP_WIDTH)+x];
}

It would be nice if I request a GetMap(8, 0) and the algorithm ignore it.

Thanks your great project. I am a newer C++, and I have a question is I have a class/object manage the map，Can I replace the GetMap with a class method?

How to use a 3D=2D(t) map with moving obstacles?

In c# code in AStarPathfinder.SortedAddToOpenList() field "inserted" is always "false".