A* Native Extension

The Defoldmine
21

my PC :slight_smile: Intel Core i7-7700K CPU @ 4.20GHz

22

Hmmm, I guess we canā€™t consider this as a weak device. What you think about the results so far?

23

Tests have shown that calling set_costs() + find_path() can be done without worrying about performance. no matter on which device it is done right? :slight_smile:

24

sure. 200000 iterations are quite high. it should be safe to use it on real-world scenarios .
Iā€™ll check out your test files tomorrow, maybe I can improve a few things(maybe doesnā€™t need to)

25

Finally I got time to fixed this little thing :slight_smile:
Updated to v 1.0.2. Added astar.toogle_zero. Default value is false so it is backward compatible.

4 Likes
26

Hi,

First of all thank you for the great extension :slight_smile:

Just want to let you know, that on current master (I noticed there are some changes cca hour ago) the pathfinding seems to be broken. I have pathfinding setup only for four direction

astar1.1
astar1.1962Ɨ672 13.5 KB

I tried to refetch version 1.0.3 and there it seems to be working

astar1.03
astar1.03962Ɨ672 11.4 KB

Only change I did is

astar.use_zero(true)

as in version 1.1 as the default is now false

1 Like
27

New version 1.1.0

This is a major release. Consider it a Beta version. The best way to test everything is to build something with it, so new examples are on the way. I hope to share a few basic examples and one complete turn-based example in the coming weeks. There might be some fixes.

Feel free to open an issue if you encounter any problems.

What is new

Screenshot 2024-06-27 at 10.30.11
Screenshot 2024-06-27 at 10.30.11639Ɨ539 92.1 KB

  • Entities: You can now target entities like potions, chests, or enemies, which were not possible to solve on the map before. You can toggle astar.use_entities() before calling the astar.solve() and astar.solve_near() methods.

As you can see in the example above, tile 4-6 is occupied, which was not possible before. Additionally, the same entities are available on different tiles

astar.solve() only includes the end/last target tile to the path result. Other entities along the path stays as not passableā€¦

astar.solve_near() includes all entities from entities table.

  • Partial code refactoring(nearly %30) for better readability, performance improvement(minimal) and Defold compatibility. Iā€™ll continue to improve it. Almost everything is now preallocated. You may hit the limits. If so, feel free to open an issue
  • astar.print_map() added. You can print the latest map state for debug purposes. It may not look appealing, but it can be quite useful.
  • astar.solve() and astar.solve_near() now also returns tile content ID.
  • astar.map_vflip() and astar.map_hflip() added. You can now flip the map. It might be helpful when importing maps from third parties, such as Tiled.
  • astar.reset() added. It cleans up everything.
  • Optional vertically flip map added to astar.setup().
  • API Documentation updated.

!! BREAKING CHANGE !!

I try not to break anything, which is why I had to make some tough decisions. So far, there is only one breaking change. Except for this minor change, even my 5-year-old examples still work.

The default value for tables and tile positions starts at 1. For backward compatibility, you can simply toggle it in astar.setup() or by using astar.use_zero(true).

Toss a Coin to Your Witcher :stuck_out_tongue:

If you find my Defold Extensions useful for your projects, please consider supporting it.
Iā€™d love to hear about your projects! Please share your released projects that use my native extensions. It would be very motivating for me.

About .script_api file update

Iā€™m sorry, but I really dislike YAML (and other tab-based languages, including Python) files. If youā€™re using the built-in editor and need autocomplete, please consider contributing to help me with this.

What is next
Iā€™m considering non-blocking (async) solvers. Nothing is planned yet, and thereā€™s no ETA. I need to do some research on this.

9 Likes
28

Ah, you are fast :slight_smile: I just update the new version and post a release notes :slight_smile:

Is it OK now when you set astar.use_zero(true) ?

29

I already did that change and with that it doesnā€™t seem to work.

These are my changes

image
image822Ɨ503 17.4 KB

30

You could try generating it? For extension-steam I created a Python script which parses cpp, h and lua files in search of annotations such as this one:

It puts all of them in a json like this one: extension-steam/api.json at master Ā· defold/extension-steam Ā· GitHub

And then uses that json and a Mustache template to spit out markdown and a .script_api file:

You should be able to copy the above three files and make a few tiny changes to get it to work for your project (assuming that youā€™ve annotated your code properly).

1 Like
31

Unfortunately, no, unless I get paid for the project(cause Iā€™m lazy). :slight_smile:
Iā€™ll consider it. Thank you.

32

I tried my old examples, and they worked well, but they all use 8 directions. Now, Iā€™m going to see if thereā€™s something different for 4 directions. Iā€™m on itā€¦

33

@septumca I just pushed the fix for this. It wasnā€™t related to 0 indexes; I simply forgot to set the default map type to classic. This is why your path zig-zags. Sorry about that :slight_smile: It should be fixed now, if you want to keep 0 indexes, you can use astar.use_zero(true)

2 Likes
34

It works perfectly now

Thank you for quick fix :slight_smile:

2 Likes
35

New Hexagonal example is here:

A*
Test it: defold-astar-hex-example 1.0

Art Credit: Kenny

You can set the map type to odd-r or even-r. odd-q and even-q types are not supported in this example.
Just set the map_type variable on main.script file accordingly.

-- SET IT TO -> astar.HEX_EVENR or astar.HEX_ODDR to see the difference 
-- See: https://github.com/selimanac/defold-astar?tab=readme-ov-file#astarset_map_typetype 
local map_type = astar.HEX_ODDR
7 Likes
36

Hello!
Iā€™m encountering an issue where entities arenā€™t being detected, and Iā€™m not sure if itā€™s a bug or if Iā€™m messing up. My understanding is that object IDs should be stored in a table (entities) and then passed to the pathfinder using astar.set_entities(entities) before calculating the path. However, when I do this, the pathfinder seems to completely ignore them.
Iā€™m using Astar v.1.1.1 and an exact copy of the ā€œBasic Tile Exampleā€ code.

Thanks for reading.

37

Iā€™m quite busy today, so I might not be able to check this out right away. But does the basic example work as expected, or does it have the same problem?

Could you please share a minimal repro case so I can take a look?

1 Like
38

Same problem with the basic example. Hereā€™s the repo in case it helps. Thank you!

1 Like
39

I just quickly checked out the basic example, and it doesnā€™t contain any entities at all. I should probably include it: GitHub - selimanac/defold-astar-tilemap-example

In your project, youā€™re passing a STRING as an entity.

I think you assumed it would somehow get the OBSTACLE game object from your collection, but it doesnā€™t work that way.

You must pass the ID of the tile, and this ID must exist in the World array: AStar.set_entities(entities)

Iā€™m going to update the basic example and let you know.

Note: Entities are not meant for generic obstacles, you can simply add obstacles directly to the tile map. Entities serve a different purpose. For example, tile ID 2 is an obstacle, and only tiles with ID 1 are walkable. You can add tile ID 3 and set it as an entity.

4 Likes
40

I completely misunderstood how entities work. Sorry for wasting your time and thank you for clarifying that for me. Have a nice day.

2 Likes