Scratch

coolstuff · 2010-05-07 18:58:19

A simple 1-sprite-1-script project which will find its way to point A to point B flawlessly, given a randomly drawn course. By flawlessly, I mean that it will (if possible) get there in the fastest number of moves.
Enjoy!
http://scratch.mit.edu/projects/coolstuff/1034493

You no longer have to download it!

Here's how it works:

Starting from the "goal" square, it numbers each of the surrounding squares as "1" "2" "3" and "4". For example (Where G is the goal, Y is the starting point and B is a wall):

Code:

##2###BY
B1G3##B#
##4#####

It always goes clockwise starting from the right, for consistency.

After that, it does the same for number 1, whichever squares it can. In the above case, there is a wall on the left, so it can't go there. The one on the right is already labelled as G, so we won't number that square. Therefore, only the squares above and below "1" can be numbered. We will continue from where we left off and number them "5" and "6:"

Code:

#52###BY
B1G3##B#
#64#####

Then we go on to square "2", and label the only one we can, the one to the right of it, as "7," continuing where we left off. We continue this until every possible square has been labelled.

Code:

+--+-+-+-+--+--+--+--+
|10|5|2|7|12|15|B |Y |
+--+-+-+-+--+--+--+--+
|B |1|G|3| 8|13|B |19|
+--+-+-+-+--+--+--+--+
|11|6|4|9|14|16|17|18|
+--+-+-+-+--+--+--+--+

Then, by starting on the starting point, you need only go towards the smallest number, because smaller the number, the closer you are to the goal. In this case, you would take 19, 18, 17, 16, 13, 8, 3, then the goal.

And that's it!

UPDATE LOG:

UPDATE #7: Calculating the route is now a LOT faster - in fact, I doubt it can go any faster. Pushing this project to the limits! Also, I fixed a few bugs, and the project is no longer 1-sprite-1-script, because the script got WAAAAY too long. Enjoy!

UPDATE #6: Fixed a bug which let you put the goal and "you" on the same square, screwing up the system.

UPDATE #5: By pressing "space" after the project has finished moving "You" to the "Goal," press space to go back and edit the obstacles and press space again to go back and do the course over again.

UPDATE #4: It now loads quite a bit faster at the beginning, by request and with help from AddZero. It also displays loading progress while it is calculating your route. Since it loads so quickly at the beginning, it no longer displays loading progress.

UPDATE #3: It now works online, with help from AddZero!

UPDATE #2: You can now delete walls by holding down 0 (that's Zero) while putting them down. Also, the squares are now considerably smaller, making room for 144 more squares - what was once an 8x6 board is now 16x12.

UPDATE #1: The board is no longer random. When it starts, you can click to put down obstacles. Then press space to put down the goal by clicking, and then put down your starting place by clicking again, and wait for you to move over to the goal!

You can also change the wait variable to make the pathfinder move faster or slower. Usually, it moves almost instantaneously, so I had to put a wait in effect. Change the variable to affect the speed - the lower the variable, the faster it moves.

Last edited by coolstuff (2010-07-25 21:28:52)

coolstuff · 2010-05-07 19:24:17

I've updated it so that you can put down walls and the start & end points yourself.

coolstuff · 2010-05-08 11:21:01

Update #2: Room for 144 more squares on the board! What was once an 8x6 board is now 16x12 - meaning there are now 192 squares instead of 48! This can truly show off the speed and accuracy of my AI.

Also, you can now delete walls if you accidentally put them down. Just hold down '0' while clicking on it!

coolstuff · 2010-05-08 16:46:39

*bumpity-bump*

Kileymeister · 2010-05-08 17:53:20

Wow, that works really well!

coolstuff · 2010-05-08 20:10:47

Kileymeister wrote:
Wow, that works really well!

Thanks!

AddZero · 2010-05-08 20:15:57

This works well, nice work!

coolstuff · 2010-05-09 08:51:23

AddZero wrote:
This works well, nice work!

Thank you! Also, thanks for you help with getting it to work online.

Last edited by coolstuff (2010-05-09 08:54:52)

coolstuff · 2010-05-09 08:57:45

I've updated it so that it now works online, thanks to AddZero.

AddZero · 2010-05-09 14:16:41

Cool! Glad I could help! Neat project, loved and faved!

Ideas:
1. Make parts run raster by duplicating and stacking parts inside repeat blocks.
for example, copy the [add "N" to squares] block 16 times then change [repeat 192 times] to [repeat 12 times]. this will speed it up a ton.

You can do more then that to repeat less or not at all, but then the script gets hard to deal with.

It might be tricky to do on other parts, but can speed it up a ton. even repeated 4 times, will help a ton.

2. Show progress on the pathfinding part, or at least, "please wait..." or "working"

awesome job!

Last edited by AddZero (2010-05-09 14:18:34)

coolstuff · 2010-05-09 14:29:47

Thanks again! I'll consider implementing that in the next version. However, the "repeat 192 times" isn't an excessively long amount of time. It takes only about 4-5 seconds max.

coolstuff · 2010-05-09 15:03:17

I've updated it to AddZero's specifications: it now shows the (approximate) progress while it loads, but it could be a little off - for example, if you have a course of a particular shape, it could stop at, say, 80%.

It also loads a LOT faster at the beginning. Thanks again, AddZero!

Lucario621 · 2010-05-09 16:31:09

So - can you explain how it works?

coolstuff · 2010-05-09 21:40:20

Lucario621 wrote:
So - can you explain how it works?

I can, tomorrow afternoon. It's really quite simple, actually.

coolstuff · 2010-05-09 21:57:13

I decided not to wait!
Starting from the "goal" square, it numbers each of the surrounding squares as "1" "2" "3" and "4". For example (Where G is the goal, Y is the starting point and B is a wall):

Code:

##2###BY
B1G3##B#
##4#####

It always goes clockwise starting from the right, for consistency.

After that, it does the same for number 1, whichever squares it can. In the above case, there is a wall on the left, so it can't go there. The one on the right is already labelled as G, so we won't number that square. Therefore, only the squares above and below "1" can be numbered. We will continue from where we left off and number them "5" and "6:"

Code:

#52###BY
B1G3##B#
#64#####

Then we go on to square "2", and label the only one we can, the one to the right of it, as "7," continuing where we left off. We continue this until every possible square has been labelled.

Code:

+--+-+-+-+--+--+--+--+
|10|5|2|7|12|15|B |Y |
+--+-+-+-+--+--+--+--+
|B |1|G|3| 8|13|B |19|
+--+-+-+-+--+--+--+--+
|11|6|4|9|14|16|17|18|
+--+-+-+-+--+--+--+--+

Then, by starting on the starting point, you need only go towards the smallest number, because smaller the number, the closer you are to the goal. In this case, you would take 19, 18, 17, 16, 13, 8, 3, then the goal.

And that's it!

Last edited by coolstuff (2010-05-09 21:57:24)

Lucario621 · 2010-05-10 16:18:24

coolstuff wrote:
I decided not to wait!
Starting from the "goal" square, it numbers each of the surrounding squares as "1" "2" "3" and "4". For example (Where G is the goal, Y is the starting point and B is a wall):
Code:
##2###BY
B1G3##B#
##4#####
It always goes clockwise starting from the right, for consistency.

After that, it does the same for number 1, whichever squares it can. In the above case, there is a wall on the left, so it can't go there. The one on the right is already labelled as G, so we won't number that square. Therefore, only the squares above and below "1" can be numbered. We will continue from where we left off and number them "5" and "6:"
Code:
#52###BY
B1G3##B#
#64#####
Then we go on to square "2", and label the only one we can, the one to the right of it, as "7," continuing where we left off. We continue this until every possible square has been labelled.
Code:
+--+-+-+-+--+--+--+--+
|10|5|2|7|12|15|B |Y |
+--+-+-+-+--+--+--+--+
|B |1|G|3| 8|13|B |19|
+--+-+-+-+--+--+--+--+
|11|6|4|9|14|16|17|18|
+--+-+-+-+--+--+--+--+
Then, by starting on the starting point, you need only go towards the smallest number, because smaller the number, the closer you are to the goal. In this case, you would take 19, 18, 17, 16, 13, 8, 3, then the goal.

And that's it!

Wow! I never would have thought of that!

Now is there a name for that method? Because I can tell it's not A*....

coolstuff · 2010-05-10 17:37:16

Lucario621 wrote:
coolstuff wrote:
I decided not to wait!
Starting from the "goal" square, it numbers each of the surrounding squares as "1" "2" "3" and "4". For example (Where G is the goal, Y is the starting point and B is a wall):
Code:
##2###BY
B1G3##B#
##4#####
It always goes clockwise starting from the right, for consistency.

After that, it does the same for number 1, whichever squares it can. In the above case, there is a wall on the left, so it can't go there. The one on the right is already labelled as G, so we won't number that square. Therefore, only the squares above and below "1" can be numbered. We will continue from where we left off and number them "5" and "6:"
Code:
#52###BY
B1G3##B#
#64#####
Then we go on to square "2", and label the only one we can, the one to the right of it, as "7," continuing where we left off. We continue this until every possible square has been labelled.
Code:
+--+-+-+-+--+--+--+--+
|10|5|2|7|12|15|B |Y |
+--+-+-+-+--+--+--+--+
|B |1|G|3| 8|13|B |19|
+--+-+-+-+--+--+--+--+
|11|6|4|9|14|16|17|18|
+--+-+-+-+--+--+--+--+
Then, by starting on the starting point, you need only go towards the smallest number, because smaller the number, the closer you are to the goal. In this case, you would take 19, 18, 17, 16, 13, 8, 3, then the goal.

And that's it!
Wow! I never would have thought of that!

Now is there a name for that method? Because I can tell it's not A*....

Not that I know of. It's the sample on Wikipedia when you search "Pathfinding."

Lucario621 · 2010-05-11 20:37:29

coolstuff wrote:
Lucario621 wrote:
coolstuff wrote:
I decided not to wait!
Starting from the "goal" square, it numbers each of the surrounding squares as "1" "2" "3" and "4". For example (Where G is the goal, Y is the starting point and B is a wall):
Code:
##2###BY
B1G3##B#
##4#####
It always goes clockwise starting from the right, for consistency.

After that, it does the same for number 1, whichever squares it can. In the above case, there is a wall on the left, so it can't go there. The one on the right is already labelled as G, so we won't number that square. Therefore, only the squares above and below "1" can be numbered. We will continue from where we left off and number them "5" and "6:"
Code:
#52###BY
B1G3##B#
#64#####
Then we go on to square "2", and label the only one we can, the one to the right of it, as "7," continuing where we left off. We continue this until every possible square has been labelled.
Code:
+--+-+-+-+--+--+--+--+
|10|5|2|7|12|15|B |Y |
+--+-+-+-+--+--+--+--+
|B |1|G|3| 8|13|B |19|
+--+-+-+-+--+--+--+--+
|11|6|4|9|14|16|17|18|
+--+-+-+-+--+--+--+--+
Then, by starting on the starting point, you need only go towards the smallest number, because smaller the number, the closer you are to the goal. In this case, you would take 19, 18, 17, 16, 13, 8, 3, then the goal.

And that's it!
Wow! I never would have thought of that!

Now is there a name for that method? Because I can tell it's not A*....
Not that I know of. It's the sample on Wikipedia when you search "Pathfinding."

I think yours is different though.... because it should be:

Code:

+-+-+-+-+-+-+-+-+
|3|2|1|2|3|4|B|Y|
+-+-+-+-+-+-+-+-+
|B|1|G|1|2|3|B|7|
+-+-+-+-+-+-+-+-+
|3|2|1|2|3|4|5|6|
+-+-+-+-+-+-+-+-+

coolstuff · 2010-05-11 21:15:20

Lucario621 wrote:
coolstuff wrote:
Lucario621 wrote:
Wow! I never would have thought of that!

Now is there a name for that method? Because I can tell it's not A*....
Not that I know of. It's the sample on Wikipedia when you search "Pathfinding."
I think yours is different though.... because it should be:
Code:
+-+-+-+-+-+-+-+-+
|3|2|1|2|3|4|B|Y|
+-+-+-+-+-+-+-+-+
|B|1|G|1|2|3|B|7|
+-+-+-+-+-+-+-+-+
|3|2|1|2|3|4|5|6|
+-+-+-+-+-+-+-+-+

No, it numbers them in order, not by distance. Mine was right - it numbers them clockwise from the right, starting at 1. No two squares should be the same. The only difference it makes is between two possible paths of equal length: it has a bias towards the top right. I adjusted it to suit my needs smile

Last edited by coolstuff (2010-05-11 21:15:55)

Lucario621 · 2010-05-12 15:07:57

coolstuff wrote:
Lucario621 wrote:
coolstuff wrote:

Not that I know of. It's the sample on Wikipedia when you search "Pathfinding."
I think yours is different though.... because it should be:
Code:
+-+-+-+-+-+-+-+-+
|3|2|1|2|3|4|B|Y|
+-+-+-+-+-+-+-+-+
|B|1|G|1|2|3|B|7|
+-+-+-+-+-+-+-+-+
|3|2|1|2|3|4|5|6|
+-+-+-+-+-+-+-+-+
No, it numbers them in order, not by distance. Mine was right - it numbers them clockwise from the right, starting at 1. No two squares should be the same. The only difference it makes is between two possible paths of equal length: it has a bias towards the top right. I adjusted it to suit my needs

That's not how the wiki does it...

At 0, the finish, it starts with two ones next to it...

Just look at the example on Wikipedia:

Code:

X X X X X X X X X X
X _ _ _ X X _ X _ X
X _ X _ _ X _ _ _ X
X S X X _ _ _ X _ X
X 6 X _ _ X _ _ _ X
X 5 6 5 X X 6 X _ X
X 4 X 4 3 X 5 X _ X
X 3 X X 2 3 4 X _ X
X 2 1 0 1 X 5 6 _ X
X X X X X X X X X X

And on Wikipedia, it's not distance either; just look at the 6 on the bottom - it's not 6 away - it's actually 4.

Perhaps you already know this, I guess. Could you make it so it's like how the example does it?

coolstuff · 2010-05-12 16:46:19

Lucario621 wrote:
coolstuff wrote:
Lucario621 wrote:

I think yours is different though.... because it should be:
Code:
+-+-+-+-+-+-+-+-+
|3|2|1|2|3|4|B|Y|
+-+-+-+-+-+-+-+-+
|B|1|G|1|2|3|B|7|
+-+-+-+-+-+-+-+-+
|3|2|1|2|3|4|5|6|
+-+-+-+-+-+-+-+-+
No, it numbers them in order, not by distance. Mine was right - it numbers them clockwise from the right, starting at 1. No two squares should be the same. The only difference it makes is between two possible paths of equal length: it has a bias towards the top right. I adjusted it to suit my needs
That's not how the wiki does it...

At 0, the finish, it starts with two ones next to it...

Just look at the example on Wikipedia:
Code:
X X X X X X X X X X
X _ _ _ X X _ X _ X
X _ X _ _ X _ _ _ X
X S X X _ _ _ X _ X
X 6 X _ _ X _ _ _ X
X 5 6 5 X X 6 X _ X
X 4 X 4 3 X 5 X _ X
X 3 X X 2 3 4 X _ X
X 2 1 0 1 X 5 6 _ X
X X X X X X X X X X
And on Wikipedia, it's not distance either; just look at the 6 on the bottom - it's not 6 away - it's actually 4.

Perhaps you already know this, I guess. Could you make it so it's like how the example does it?

Well, I would, but it's a lot easier the way I do and it and doesn't make any difference whatsoever smile Except if there are two paths of equal distance, which one it will choose.

AnnoyingOrange · 2010-05-12 17:02:10

This is a fun game! Great job at making everything!
Your friend,
Annoying Orange

coolstuff · 2010-05-12 17:16:57

AnnoyingOrange wrote:
This is a fun game! Great job at making everything!
Your friend,
Annoying Orange

Thanks!

waveOSBeta · 2010-05-12 17:17:51

Can you please make a graphic ad for my magazine?

coolstuff · 2010-05-12 17:43:30

waveOSBeta wrote:
Can you please make a graphic ad for my magazine?

I could. If you'd like.

And update #5 is up, allowing you to go back and edit the board after the project has run it's course.

Scratch

archived forums

#1 2010-05-07 18:58:19

Pathfinder AI

Code:

Code:

Code:

#2 2010-05-07 19:24:17

Re: Pathfinder AI

#3 2010-05-08 11:21:01

Re: Pathfinder AI

#4 2010-05-08 16:46:39

Re: Pathfinder AI

#5 2010-05-08 17:53:20

Re: Pathfinder AI

#6 2010-05-08 20:10:47

Re: Pathfinder AI

Kileymeister wrote:

#7 2010-05-08 20:15:57

Re: Pathfinder AI

#8 2010-05-09 08:51:23

Re: Pathfinder AI

AddZero wrote:

#9 2010-05-09 08:57:45

Re: Pathfinder AI

#10 2010-05-09 14:16:41

Re: Pathfinder AI

#11 2010-05-09 14:29:47

Re: Pathfinder AI

#12 2010-05-09 15:03:17

Re: Pathfinder AI

#13 2010-05-09 16:31:09

Re: Pathfinder AI

#14 2010-05-09 21:40:20

Re: Pathfinder AI

Lucario621 wrote:

#15 2010-05-09 21:57:13

Re: Pathfinder AI

Code:

Code:

Code:

#16 2010-05-10 16:18:24

Re: Pathfinder AI

coolstuff wrote:

Code:

Code:

Code:

#17 2010-05-10 17:37:16

Re: Pathfinder AI

Lucario621 wrote:

coolstuff wrote:

Code:

Code:

Code:

#18 2010-05-11 20:37:29

Re: Pathfinder AI

coolstuff wrote:

Lucario621 wrote:

coolstuff wrote:

Code:

Code:

Code:

Code:

#19 2010-05-11 21:15:20

Re: Pathfinder AI

Lucario621 wrote:

coolstuff wrote:

Lucario621 wrote:

Code:

#20 2010-05-12 15:07:57

Re: Pathfinder AI

coolstuff wrote:

Lucario621 wrote:

coolstuff wrote:

Code:

Code:

#21 2010-05-12 16:46:19

Re: Pathfinder AI

Lucario621 wrote:

coolstuff wrote: