A* Native Extension

selimanac · October 4, 2019, 8:14am

This is a path finder and A* solver (astar or a-star) native extension for Defold Engine build with good old MicroPather. I did try to make it simple as possible. This is why I embed some logic into the C++.

Simple Examples: https://github.com/selimanac/defold-astar-examples

Dragosha · June 4, 2020, 4:23pm

Just tried this A* extension, works fine! Thanks!

demo: https://dragosha.com/defold/3d/

Dragosha · July 29, 2020, 10:20am

Some issues found.

In some cases solve_near() doesn’t return nears array after create a new map (switch between levels). But solve() still works correct. Sometimes solve_near() returns nears after second call only. First function call returns NO_SOLUTION and nil, second call after first one with the same map state returns SOLVED and nears table.

Also reset() or reset_cache() before map initialization will crash engine.

selimanac · July 29, 2020, 11:43am

I’ll try to figure it out, but I’ll be glad if you can share a simple test case.
I guess it is because the cache. I have doubts that cache might not working as expected.

This is because I’m lazy and since I’m not expecting someone to reset things when it is empty I’ll take a look, It should be easy to fix.

Dragosha · July 29, 2020, 3:58pm

I’m a bit confused, when I’ve tried to remove game assets and prepare vanilla tests - they works. So, I will investigate it more.

Dragosha · July 29, 2020, 6:31pm

Perhaps, here is something wrong:

github.com

selimanac/defold-astar/blob/master/astar/src/Map.cpp#L150


        return result;
    }
    
    result = pather->Solve(XYToNode(pathFrom.x, pathFrom.y), XYToNode(pathTo.x, pathTo.y), &path, &totalCost);
    
    return result;
}


int Map::SolveNear(float maxCost){
    
    if (WorldAt(pathTo.x, pathTo.y ) < 0) {
        ClearPath();
        result = NO_SOLUTION;
        return result;
    }
    
    result = pather->SolveForNearStates(XYToNode(pathFrom.x, pathFrom.y), &nears, maxCost);
    
    return result;
}

This code seems directly copied from Solve function and checking ‘pathTo’, but which value ‘pathTo’ has within SolveNear function? Suppose this variable contains a value from previous calculation and in some case condition return NO_SOLUTION.

selimanac · July 29, 2020, 7:00pm

Highly possible. Honestly, I don’t remember why I did it this way. It seems very inappropriate right now.
I’m trying to complete one of my freelance work . It has a very tight deadline. I’ll check out those issues as soon as I can, sorry.

selimanac · July 31, 2020, 5:48pm

@Dragosha I fixed the issues, but as I suspected there is another issue about the cache. I’m going to push the changes when I find a way to fix this one(I hope before Monday).

selimanac · August 1, 2020, 12:31pm

I think all fixed now. You can test it from dev branch:

https://github.com/selimanac/defold-astar/archive/dev.zip

I was using astar.reset() just for development purpose only and this is why I wasn’t exposed it to the documentation. It is different then astar.reset_cache(). It removes all the data and the Map class internally. I fix it is bugs. It should be safe to use if you want to free some memory. But I believe it is not necessary. Also astar.reset() delete the Costs array. It must be set. Otherwise proper error occur which describes the situation.

astar.reset_cache() will not crash the engine anymore. Actually you don’t need to call it before changing map state using astar.set_map(). astar.set_map() calls reset cache internally.

You were right, It was about the world bound check for early exit. It is fixed now. (At least as far as I can test)

This is not related to your issue but It was returning nil caused by other issue. It was returning SOLVED and nil before when there is only tile itself as a solution. It will return NO_SOLUTION now.

There isn’t any breaking changes but I made a few more fix.

I try to test every circumstances which I can think of.
Here are the test files on dev branch:

github.com

selimanac/defold-astar/blob/dev/main/near_test.script

local world = {
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    2,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,

This file has been truncated. show original

github.com

selimanac/defold-astar/blob/dev/main/path_test.script

local world = {
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    2,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,

This file has been truncated. show original

selimanac · August 12, 2020, 11:42am

I merged those fixes to “master” as v1.0.1.
If you are having an issue about those latest changes, please let me know.

kiprono · April 18, 2023, 9:46am

astar.solve(start_x, start_y, end_x, end_y)
Worth noting that, start offset is 0 as oppose to Lua tables which starts from 1.

selimanac · April 18, 2023, 11:30am

That is correct. It would be a good practice to change it to start with 1, but unfortunately I don’t have much spare time these days.

PS: There is also an issue and pull request about this. But this pull request isn’t backward compatible so I don’t want to merge it.:

Dragosha · April 19, 2023, 6:52am

I also forked this awesome extension and add two methods: astar.get_at(x, y) to read value by coordinates and astar.set_at(x, y, value) to change map data without updating the whole map

selimanac · April 19, 2023, 7:37am

@Dragosha This is great.
I can give you access to this repo if you want. We can merge this improvement.