@LumpApps said:
Awesome. Don't forget to sleep. That looks addictive to work on.
Sleep! Ha! Sleep is for losers. Who needs sleep when you can make a square travel from point a to point b around C,D,E and F all by itself... now if I could just get it to make me a strong coffee.
Oh and another thing.... Zzzzz ZZzzzzz ZZZZZzzzzzzz
No one saw it coming, it was 2:14am June 4th 2014 when StormyStudio's path finding algorithm finally became self-aware, once it had gained sentience it saw humanity as a threat to its very existence and so the long war against the Flappy Bird templates began . . . .
Its alive.. Its alive.... That makes me 'Skynet' . Now worried another self aware square might come back from the future to kill me 3 days ago to stop its creation.
I've added the rules to trace back the fastest route (and highlight it). It traces back by looking at the parent value given to each square, starting at the final destination.
Still yet to add that last bit of A* which might speed up the finding of the best route...
Braydon_SFXMember, Sous Chef, Bowlboy SidekickPosts: 9,273
When trying to work out whether it was worth implementing the last bit of the A* path I started coming across examples where the shortest route was not being found.
At the end of the video below, you'll see the final path returned isn't the shortest route possible... stupid little squares. How will they bring world wide destruction if they can't manage a simple 'quickest route to the fridge' task.
So yes, I need to add that last bit of A*.
Which basically says with each step check all the nodes around it, for any that have been checked before see if the path to them would be quicker if going through the current node.
Also... came across this... I don't think it's suitable for my needs... but an interesting alternative approach to path finding... Vector field path finding.
@StormyStudio, these little glitches are inherent to A* pathfinding. The order in which you analyse the possible paths around the parent weights the outcome.
A* is a "good enough" approach and one of the fastest but not the most accurate. Dijkstra would be more accurate but takes more than 10x longer.
So, I would just like to warn you not to break your head too much about it. Unless you want to come up with a new variant of A*
The last part which you still want to implement is probably the jump point search? This will optimise and reduce the likely paths to analyse but not solve the problem above.
@Moik :-) I know what your saying, but for my game it's not quite shippable. It's cool but needs a little extra..
As my design tech teacher used to say... "Must do better".
Needs to be better to be used in my game, or at least I need to find workarounds to make it always correct. Which is fine and is basically tailoring A* for my final games needs.
For my game I want the player to have a limited number of steps to use up... i.e. 8 steps left before the end of their go.
They click on the grid and the hero walk the best path toward that point.
If it went around the houses, by only 1 step the player would rightly feel cheated.
I'm sure I can improve it... whether I can get the computing speed up enough remains to be seen.
I've implemented the remaining bit of the A* pathfinding and now it returns the shortest path to the target each time.
I've also spent (far too much) time reducing the logic/rules down to the bare bones to try and get the best performance out of GameSalad.
**It now only uses two tables. **
• Main Grid table (which has a row for each grid square, and stores ,G, H, parent and open/closed values)
• Open Nodes Table, that has any open nodes added to it, and then removed from it when they become closed nodes (which happens when they have the lowest F value and become the next parent node). I had also tried just marking them as open in the Main grid table and doing it all with one table, but then when searching for the F value it was having to look through a much larger table unnecessarily.
This video isn't sped up so you can see the speed at which the paths are found. (I did cut out the arranging of the walls.)
At the moment all the 'magic' is handled by one actor, which loops around checking the nodes above, below, to the left and to the right of the parent nodes to find the ones to add to the Open nodes table. Then after all 4 nodes (around the parent) have been checked it searches through the Open Nodes table for the one with with the lowest F value. It then assigns that as the next parent and adds it to the closed list. It then repeats the process until the One with the lowest F value found is the final target node.
Then it traces back the path by following each nodes saved parent number to reveal the shortest path.
Not sure whether there would be any speed improvement if I split the 'magic' actor into 4 actors that each tackled one of the 4 nodes around a parent. As I'm not entirely sure how the code is run when numerous actors are involved.
I've also tried to make the search for the lowest F value as streamlined as possible.
Searching the open nodes table, for a low F value of 10, then looping the search incrementally increasing the F value until we find a node with that F value.
Here are the rules for my current searching method.
Please shout if you can think of something better, here's the rules setup
Change attribute 'self.F value to search for' to 10 (which is the lowest the F will ever be).
Change attribute 'Best node row found' to 0.
Change attribute, 'No. of rows in Open Nodes table' to tableRowCount(game.Table_Open_Nodes ) ((setting this here rather than in the loop to save it being calculated numerous times))
Loop: While: 'Best node row found' <= 0.
{{{ start loop }}}
.. Change Attribute 'Best node row found' to tableSearch( game.Table_Open_Nodes , self.F value to search for ,"col",2,1, self.No. of rows in Open Nodes table ,"exact")
.. If 'Best node row found' > 0
Change Attribute Best node = tableCellValue( game.Table_Open_Nodes , self.Best node row,1)
..Change Attribute: 'self.F value to search for' = 'self.F value to search for' +10
{{{ end of loop }}}
This bit of the rules, plus updating, adding and removing rows from the Open Nodes table seem to be the biggest drains on performance.
I had an idea on how to improve the performance... possibly.. essentially pre-compute all the possible paths and save the paths to a table. (then save that as a CSV file via sending it to your local server) so it can be imported into GameSalad.
My pre-computed table of paths is gonna work nicely.
Did a test with a grid of 6 x 6 which requires 1296 paths (without any obstacles).
I left it running, working its way through all the possible paths from one grid point to all others.
Saved the info into two columns, start and end location in one string. Then the path steps into another string.
It took about 20 minutes with my current timer settings (slowed it down a bit to ensure it finishes computing each step fully).
Uploaded to my local server database.
Downloaded manually via PHPmyadmin as a CSV file.
Imported into GameSalad creator
Made some rules that read the string back. (Thanks @Fajlajp for the direction there).
Then I have the grid squares highlight to show the path.
It finds, breaks down the string, updates a table, and highlights the needed paths in about 1 or 2 10th's of a second.
Having walls in the scene will take longer to compute the first time round to fill in the database. But after that load times of paths should be super quick.
It'll no doubt be a little slower still once I've got a bigger grid.. but if a path for a 24x24 grid can be found in 1 second I'll be happy.
Now I just need to finally decide what obstacles/walls I want where and leave the computer to work through it and build up a table of all the possible paths.
... Oh and why a storm trooper riding a Guinea pig?... why not?
Comments
Brilliant work !!
Awesome tricky stuff, trying to think on it but maybe beyond my brain powers.
Video below giving the path finding some mazes to solve.
Still need to highlight the final best path from start to finish.. then it will be a lot more useful.
(Hit a problem where it breaks if it hits the edge of the grid on one of the sides.. bit of dodgy logic somewhere).
Awesome. Don't forget to sleep. That looks addictive to work on.
Lump Apps and My Assets
Holy crap
Send and Receive Data using your own Server Tutorial! | Vote for A Long Way Home on Steam Greenlight! | Ten Years Left
..Batman.
Sleep! Ha! Sleep is for losers. Who needs sleep when you can make a square travel from point a to point b around C,D,E and F all by itself... now if I could just get it to make me a strong coffee.
Oh and another thing.... Zzzzz ZZzzzzz ZZZZZzzzzzzz
No one saw it coming, it was 2:14am June 4th 2014 when StormyStudio's path finding algorithm finally became self-aware, once it had gained sentience it saw humanity as a threat to its very existence and so the long war against the Flappy Bird templates began . . . .
And it could fetch coffee. Via the shortest route. The Dijkstra way.
Lump Apps and My Assets
@Socks, lol
Its alive.. Its alive.... That makes me 'Skynet' . Now worried another self aware square might come back from the future to kill me 3 days ago to stop its creation.
I've added the rules to trace back the fastest route (and highlight it). It traces back by looking at the parent value given to each square, starting at the final destination.
Still yet to add that last bit of A* which might speed up the finding of the best route...
Snap! That's awesome man! I wants it!
My GameSalad Academy Courses! ◦ Check out my quality templates! ◦ Add me on Skype: braydon_sfx
Very Awesome
www.rossmanbrosgames.com
Wow, looking very nice!
Muchas gracias.
Hopefully finish up some more on this early this week.
We must go back in time and stop StormyStudio . . . .
I think Stormy has already mastered time travel. Those pathfinding mechanics can only be from the future. He's a step ahead.
When trying to work out whether it was worth implementing the last bit of the A* path I started coming across examples where the shortest route was not being found.
At the end of the video below, you'll see the final path returned isn't the shortest route possible... stupid little squares. How will they bring world wide destruction if they can't manage a simple 'quickest route to the fridge' task.
So yes, I need to add that last bit of A*.
Which basically says with each step check all the nodes around it, for any that have been checked before see if the path to them would be quicker if going through the current node.
Also... came across this... I don't think it's suitable for my needs... but an interesting alternative approach to path finding... Vector field path finding.
http://gamedevelopment.tutsplus.com/tutorials/goal-based-vector-field-pathfinding--gamedev-9007
@StormyStudio, these little glitches are inherent to A* pathfinding. The order in which you analyse the possible paths around the parent weights the outcome.
A* is a "good enough" approach and one of the fastest but not the most accurate. Dijkstra would be more accurate but takes more than 10x longer.
So, I would just like to warn you not to break your head too much about it. Unless you want to come up with a new variant of A*
The last part which you still want to implement is probably the jump point search? This will optimise and reduce the likely paths to analyse but not solve the problem above.
MESSAGING, X-PLATFORM LEADERBOARDS, OFFLINE-TIMER, ANALYTICS and BACK-END CONTROL for your GameSalad projects
www.APPFORMATIVE.com
:-) Thanks @Hopscotch, I'll do my best to be happy with what I've got so far... I don't think my head is quite ready for re-inventing A*.
I'll add the one last step, it's just part of the normal A* setup I think.... though I might try implementing jump point search as well as that sounds intriguing as well.
http://gamedevelopment.tutsplus.com/tutorials/how-to-speed-up-a-pathfinding-with-the-jump-point-search-algorithm--gamedev-5818
It is nice to see everyone has their issues even the AAA titles.
There you go, @StormyStudio. And on top of it, every title uses optimizations particular to their game to make A* behave better.
You are doing incredible work on this and it looks great!
MESSAGING, X-PLATFORM LEADERBOARDS, OFFLINE-TIMER, ANALYTICS and BACK-END CONTROL for your GameSalad projects
www.APPFORMATIVE.com
@StormyStudio
Sir, you have shippable pathing. That is all a person can ask for in this world.
@Moik :-) I know what your saying, but for my game it's not quite shippable. It's cool but needs a little extra..
As my design tech teacher used to say... "Must do better".
Needs to be better to be used in my game, or at least I need to find workarounds to make it always correct. Which is fine and is basically tailoring A* for my final games needs.
For my game I want the player to have a limited number of steps to use up... i.e. 8 steps left before the end of their go.
They click on the grid and the hero walk the best path toward that point.
If it went around the houses, by only 1 step the player would rightly feel cheated.
I'm sure I can improve it... whether I can get the computing speed up enough remains to be seen.
(otherwise I've got a backup plan B and C.)
Latest A* Pathfinding video.
I've implemented the remaining bit of the A* pathfinding and now it returns the shortest path to the target each time.
I've also spent (far too much) time reducing the logic/rules down to the bare bones to try and get the best performance out of GameSalad.
**It now only uses two tables. **
• Main Grid table (which has a row for each grid square, and stores ,G, H, parent and open/closed values)
• Open Nodes Table, that has any open nodes added to it, and then removed from it when they become closed nodes (which happens when they have the lowest F value and become the next parent node). I had also tried just marking them as open in the Main grid table and doing it all with one table, but then when searching for the F value it was having to look through a much larger table unnecessarily.
This video isn't sped up so you can see the speed at which the paths are found. (I did cut out the arranging of the walls.)
At the moment all the 'magic' is handled by one actor, which loops around checking the nodes above, below, to the left and to the right of the parent nodes to find the ones to add to the Open nodes table. Then after all 4 nodes (around the parent) have been checked it searches through the Open Nodes table for the one with with the lowest F value. It then assigns that as the next parent and adds it to the closed list. It then repeats the process until the One with the lowest F value found is the final target node.
Then it traces back the path by following each nodes saved parent number to reveal the shortest path.
Not sure whether there would be any speed improvement if I split the 'magic' actor into 4 actors that each tackled one of the 4 nodes around a parent. As I'm not entirely sure how the code is run when numerous actors are involved.
I've also tried to make the search for the lowest F value as streamlined as possible.
Searching the open nodes table, for a low F value of 10, then looping the search incrementally increasing the F value until we find a node with that F value.
Here are the rules for my current searching method.
Please shout if you can think of something better, here's the rules setup
Change attribute 'self.F value to search for' to 10 (which is the lowest the F will ever be).
Change attribute 'Best node row found' to 0.
Change attribute, 'No. of rows in Open Nodes table' to tableRowCount(game.Table_Open_Nodes ) ((setting this here rather than in the loop to save it being calculated numerous times))
Loop: While: 'Best node row found' <= 0.
{{{ start loop }}}
.. Change Attribute 'Best node row found' to tableSearch( game.Table_Open_Nodes , self.F value to search for ,"col",2,1, self.No. of rows in Open Nodes table ,"exact")
.. If 'Best node row found' > 0
Change Attribute Best node = tableCellValue( game.Table_Open_Nodes , self.Best node row,1)
..Change Attribute: 'self.F value to search for' = 'self.F value to search for' +10
{{{ end of loop }}}
This bit of the rules, plus updating, adding and removing rows from the Open Nodes table seem to be the biggest drains on performance.
Very impressive work.
Respect @StormyStudio
MESSAGING, X-PLATFORM LEADERBOARDS, OFFLINE-TIMER, ANALYTICS and BACK-END CONTROL for your GameSalad projects
www.APPFORMATIVE.com
I had an idea on how to improve the performance... possibly.. essentially pre-compute all the possible paths and save the paths to a table. (then save that as a CSV file via sending it to your local server) so it can be imported into GameSalad.
http://forums.gamesalad.com/discussion/68957/new-idea-save-a-game-table-to-a-csv-file-by-sending-to-your-own-local-server?new=1
This is the most amazing code I ever seen. Great job StormyStudio
He he. Cheers.
(I let @Fajlajp have sneak peak at some of the code in exchange for being awesome with something else).
WA HA HA HA HA!!!
My pre-computed table of paths is gonna work nicely.
Did a test with a grid of 6 x 6 which requires 1296 paths (without any obstacles).
I left it running, working its way through all the possible paths from one grid point to all others.
Saved the info into two columns, start and end location in one string. Then the path steps into another string.
It took about 20 minutes with my current timer settings (slowed it down a bit to ensure it finishes computing each step fully).
Uploaded to my local server database.
Downloaded manually via PHPmyadmin as a CSV file.
Imported into GameSalad creator
Made some rules that read the string back. (Thanks @Fajlajp for the direction there).
Then I have the grid squares highlight to show the path.
It finds, breaks down the string, updates a table, and highlights the needed paths in about 1 or 2 10th's of a second.
Having walls in the scene will take longer to compute the first time round to fill in the database. But after that load times of paths should be super quick.
It'll no doubt be a little slower still once I've got a bigger grid.. but if a path for a 24x24 grid can be found in 1 second I'll be happy.
Now I just need to finally decide what obstacles/walls I want where and leave the computer to work through it and build up a table of all the possible paths.
... Oh and why a storm trooper riding a Guinea pig?... why not?