@Purp13 if you add the tilemap extension, there is a “location of sprite” block that you can use with this extension to do that.
1 Like
How do you do that?
I found out how to do it
Here’s an example:
4 Likes
Well i did but it only moves to the location that the player spawns at and doesn’t go to the players current location
I figured it out when you add a on every game update then it will then update where the location of the players so it will go to the player
I’m also having trouble with the player taking damage when the enemy is touching
Be careful doing it in an on game update! Path finding sometimes takes a really long time and if you do it too often it will slow your game down quite a bit.
2 Likes
How do you get rid of the strange purple square
I installed the wrong version
but how could I use this to have an enemy chase a player?
Hi Joey
I am using this extension recently. I know you all are so buy, so to make it can be call frequently, I forked and did some optimization for the “a-star” function.
https://github.com/aqeeaqee/arcade-tilemap-a-star/
On Meobit, comparing current verision, optimized a-star faster about 90% in most time, and faster 70% if there’s no way to get target location.
Here is a screen shot on Meobit, ran 200+ times. Upper part of red dots looks like a 45° line, so running time can be estimated easily, e.g. 30 steps path will cost about 30+ms.
- red dots for optimized, yellow for origin
- dot x= time used in millisecond, y= steps count of path
Looking forward for you review and feedback, hope you like it.
And hope it is useful for all guys here.
2 Likes
Woops sorry missed the notification here, changes all look good from what I can tell (would have to spend a few minutes reasoning out if the changes in costs would potentially change any path choices, but it should be fine / at worst it would be ‘close enough’ to optimal) – if you want to make a PR replacing the old one with your modifications I can double check and merge!
1 Like
Hi Joey!
I am so happy that you are satisfied with these changes! Thanks!
And I am very glad to explain the reason about costs, or even any more details if you are interested.
about costs changes:
-
cost of Heuristic (I guess you mean this):
according to a* algorithm, it should be the short distance from current spot to target. In real map, we estimate the distance with the length of a streight line from current spot to target, there are no other choice(say no pre-data of routes). In our tilemap, particularly, walking direction are limited(8), so the length of possible shortest path connecting these 2 spot would like:
So we got:
costHeuristic = shortest path length
= LengthOfLongerSide - LengthOfShortSide + LengthOfShortSide * 1.414
= LengthOfLongerSide + LengthOfShortSide * 0.414
Then, to avoid float multi calculation, scale all costs up by 1000:
=LengthOfLongerSide * 1000 + LengthOfShortSide * 414
- BTW, for cost calculation of each step:
const neighborCost = currLocation.cost + 1000;
const cornerCost = currLocation.cost + 1414
-
total cost = cost/factorOfWeight + costHeuristic
the factorOfWeight make cost more important than the costHeuristic. It’s a experimental number relative to the number and shape of paths on the map, 10 or more can all make it faster about 50%. -
the comparator of the Heap , I changed to:
(a.cost + a.extraCost) - (b.cost + b.extraCost),
from(a.cost ** 2 + a.extraCost) - (b.cost ** 2 + b.extraCost), cause I thought this is just a typo when the commit “avoid sqrt …”, correct me please if not.
Waiting for your review for above, and then I will create a PR, if all of these are OK for you.
Feel free to ask me please, if there is anything I didn’t explain clearly(sorry for my poor english) or any thing you are interesting.
2 Likes
Perfect explanation / confirmation, sounds right! I was almost entirely concerned with the comparator change / understood the approximation you made for the edge costs right away, but yeah I think you’re right that the comparator change was a typo after re-reading the code for a moment – it’d just been a while since I reasoned through the path finding logic so I assumed the existing code had some basis hah.
Thanks again~
1 Like
Yeh, I can understand that, one can’t remember every details after such a long time, especially you all are so busy everyday.
And you are welcome, it’s my pleasure to contribute some codes for the wonderful Arcade platform. Thanks for the nice job of you and all members of Aracde team!
I will prepare and create PR soon. See you on the Github!
1 Like
Hi Joey
PR created, may I have your review please
Brief overall:
By now, 7% averaged running time on simulator comparing with origin version, and 10.5%(2.4ms average) on Meowbit. Averaged with 10000+ calling results, with random start/target spot in a 32x32 tilemap(see snapshot below)
Except the changes metioned in prev post, also did some other changes of following:
- Replaced the Heap with a regular Array,(so sorry
), but it faster indeed, may because less memory used I guess. 50% on sim, and 98.5% on Meowbit comparing with latest version. - And all the tiles.Location instance replaced by a SimpleLocation which has only col/row properties, and make it faster too, 85% on Meowbit.
- The factorOfWeight was removed, for I found it may output detour path, though it can make it faster very much. Didn’t noticed cause I focused on perf only until I wrote the validate&drawing functions.
totalCost = cost/factorOfWeight + costHeuristic→totalCost = cost+ costHeuristic
PS. to keep the test.ts file clean for final users, I kept the different implementations and comparation codes in my repo, and commented with perf result I collected. Check it if you or anyone have interesting on them. Change the namespace of the aStar function in main.ts, you can campare any two of these implementations.
1 Like
Gave it a review and looks great! Only a few things that are probably like ~5-10 minutes total and then I’ll merge it after you get time~ thanks again
1 Like
Hi all
All changes above has updated to this extension, with Joey’s great help.
New edition v0.4.0 has released, you can update to new version by click refresh button beside the extension name in JS mode. Or check the extension repo for details.
Any question/feedback are always welcome!
Hi Joey, thank you created this great extension!
And I am really happy having a chance to make it better!
2 Likes
Can this be used in a 2D side scrolling game with gravity?
Not really in it’s current form. A* is a pretty general path finding algorithm, but the implementation written here is just written for a top down path following – e.g. for a character to escape a maze. It would require modification to work as AI for a normal side scrolling game – e.g. it’d have to be written to know that movement left, right and down is fine, but for up can only be done in an arc (and to account for enemies, using powerups, etc). Here’s an example of someone who wrote an A* implementation to control mario in a game: https://www.youtube.com/watch?v=DlkMs4ZHHr8
That said, it could definitely be used in a 2d side scrolling game – you could make it so bat like enemies, which will ignore gravity, follow the player around when nearby, or to make projectiles that hone in on the player or enemies without being to cheaty (e.g. just fire at the current location of the player and not update each time), and the base of the javascript would be very similar if you were to write an ai for mario – you’d have to update how edges are considered & add other heuristics / account for enemies as nodes in the graph too.
1 Like