Sign Up, Lost Password
Comments for Path Finding
Return to Path Finding
Really good scenario, hope it's okay that I used the turtle code for one of my own scenarios. I have been working with this code for some time and I think I found one bug. In the turtles check method you have written: if (sqrList.get(i).isClosed() && sqrList.get(parent).getG() + cost < sqrList.get(i).getG()) // Check if new route to square is better Here the 'problem' is sqrList.get(i).isClosed(). If you take the turtle to (8,6) and then click on (9,3) you will see that the turtle moves in zigzag. If you remove the 'problem' the turtle will move straight up to (8,4) and then to the goal (9,3). I would love to know if this piece of code is there for a reason or if it's a mistake.
Yes feel free to reuse the code. Thanks for the catch! Just looking at it briefly, it seems it should have '!'. I have reused this code for many of my scenarios, overlooking that bug! Ha! Many thanks =) if (!sqrList.get(i).isClosed() && sqrList.get(parent).getG() + cost < sqrList.get(i).getG())
A new version of this scenario was uploaded on Mon Jul 01 00:14:45 UTC 2013 Bug fix
I hope I may use this in a new game, because this is awsome and perfectly fits my game! And shall I also put your name in the credits under 'special thanks' then?
A new version of this scenario was uploaded on Fri Nov 22 19:23:54 UTC 2013 Preparation for a project coming soon.
What in the world is this new project that involves all of your scenarios?
I don't want to reveal too much, but user unique codes found in my other scenarios will unlock things in my new project. And it's in its final stages of development. =)
BUT, these codes won't appear until my new project is ready to be released. And I will not need to update all my other scenarios again to enable the codes.
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.
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.
@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.
@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.
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)
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.
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.
Not easy to drop such points in a random generated world. ;)
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.
@Builderboy2005, my big project (Residents) has now been uploaded.