This site requires JavaScript, please enable it in your browser!
Greenfoot back

Report as inappropriate.

bourne
bourne presents ...

2013/5/5

Path Finding

Example of A* path-finding algorithm

Click for turtle to move there.

Feel free to reuse the code here.

5790 views / 1468 in the last 7 days

8 votes | 0 in the last 7 days

Tags: simulation demo with-source path-finding bourne

open in greenfoot

There is no HTML 5 translation of this scenario available.
View legacy version (requires Java plugin)

This scenarios uses Java features that are not available for use after conversion to HTML 5. Please try the legacy version, which requires the Java plugin to be installed.

that's an interesting idea, I hide little easter eggs in my source code every now and then, but i haven't thought of using codes inside my source code for another project.
RUMMAKERRUMMAKER

2013/12/22

I swear programming never gets easier Dx. trying to implement this into my game made my brain melt. Question: how efficient is a* pathing for a big grid(like 50 by 40) with around 200 actors using pathing.
bournebourne

2013/12/23

@RUMMAKER, programming is hard, but you should gain readiness to tackle new problems as you worked through a variety of past problems. And think about a* this way: it may have to check many cells (max: 50*40=2000). But this is only done to find a path, typically an Actor won't be calculating while traveling. So maybe your 200 Actors won't be trying to calculate a path at the same time. I never attempted to test the efficiency of the algorithm in terms of load. I used it in my Specter game and it seemed to not lag anything with a number of objects (probably < 50) in a relatively large area, while I think I had the objects recalculate path to the player when they reached halfway through their current calculated paths.
bournebourne

2013/12/23

@RUMMAKER, also - I imagine the algorithm would really only slow things down as the paths turn out to be really long, with many long branches that were promising at getting you to the destination and ended up not contributing.
RUMMAKERRUMMAKER

2013/12/23

thx for the reply, I have another question, I was looking up a* on the web and they all used an arrayList for the closed list while you used a boolean. Which way is more efficient? (oh and my brain is still melting)
bournebourne

2013/12/23

I'm not sure what an ArrayList would do for a closed list, besides holding all the closed squares - which when determining if it contains something, would be a linear search. It's been a while since I looked at this project, but it seems the boolean is pretty straight forward when checking neighbors at a cell.
lordhersheylordhershey

2013/12/23

You do not have to map out every cell you can cheat at searching by dropping points in the center of most generic areas of interest just make sure there is a path between the points, and then once in the general area you can use a more refined search.
Super_HippoSuper_Hippo

2013/12/23

Not easy to drop such points in a random generated world. ;)
lordhersheylordhershey

2013/12/23

I was trying to rack my brain to what the optimized A* search was, I found this buried in my bookmarks: http://harablog.wordpress.com/2011/09/07/jump-point-search/ might be useful.
bournebourne

2013/12/31

@Builderboy2005, my big project (Residents) has now been uploaded.

See all comments

Want to leave a comment? You must first log in.

Who likes this?

Amri MrHam RUMMAKER vladdes JetLennit SPower Game/maniac Zamoht