Why use A Star Odyssey?
The pathfinding algorithm is a basic element of in game design. Coding a pathfinding algorithm in Scratch is very hard, and running efficiency is extremely low. Hence the necessity for high-efficient pathfinding extension for Scratch is urgent. A Star Odyssey will definitely help you if you want to…
- make an RPG game. The hero will find the path when the user clicks a point on the map.
- make an open-world game. The guidelines for the mission will be displayed on the map to indicate the right direction.
- make a fighting game. You can design a smart armor that has bullet lock and follows the player automatically.
Most importantly, the A Star Odyssey extension is extremely easy to use and has very high performance.
Best Practices
[ coming soon ]
Modules
A Star Odyssey contains five modules:
Module | Description |
🔧 Setup | Create obstacles and load them on a map
Clear obstacles on a map |
🚫 Obstacle | Test if a coordinate point is walkable or not
Test if current sprite target is walkable or not |
🛰 Path Finding | Find a path on a map from the start point to the endpoint and output the result as a list |
📝 Utils | Utilities to help you change the position of sprites more easily or get x y positions in the path list |
💬 Debug | Draw the obstacle map and workable path on a canvas |
Before you get started, you can find a button on the debug module called Toggle Debug Window. Click it to open or close the debug window. This is very useful for debugging.
Functions and Definitions
🔧 Setup
Load an obstacle onto a map
To load an obstacle onto a map is very simple, just choose a sprite and its costume number. You don’t have to display the sprite on the stage.
When an area on the costume is transparent, it will be marked as a workable area or an obstacle.
Parameter | Description | Example Value |
map name | The map name. You can add more than one obstacle to the same map or create more than one map in your game. | obstacle |
Obstacle Sprite | The sprite you want to load as an obstacle | Sprite 1 |
Costume # | The costume number, starting from 1 | 1 |
dX | The x position offset, relative to the center of the sprite’s costume | 0 |
dY | The y position offset, relative to the center of the sprite’s costume | 0 |
scale | The scale of the costume | 100 |
Take the Scratch cat as an example.
In the debug window,
the green color represents the walkable area,
the red color represents the wall or obstacle area,
and the blue line indicates the found path.
If you want to load two costumes as obstacles on the map. Code like this:
In this example, we loaded three costumes to one map called obstacle. The first is in the center of the map and keeps a 1:1 scale. The second is moved 100 px to the left and keeps a 1:1 scale. The third is moved 150px to the right and scaled up to 150%. The map will be like this:
Clear a map
Clear a rectangle on the map. In this case, as shown above, all obstacles will be cleared.
If you want to clear the upper half part of the map, use the code demonstrated below:
🛰 Path Finding
Once you have a map, you can now find a path on the map.
Find a path and output the result as a list
You have two ways to find a path, by giving two coordinates or two sprites’ targets.
For example, we want to find the path from point (-320,180), which is the upper-left corner of the map, to point (319,-179), which represents the bottom-right corner of the map. As the result, we output it as a list in Scratch.
The pathfinding result will be shown like this:
Parameter | Description | Example Value |
map name | The map that you want to use to find the path | obstacle |
from x | The x position of the start point | -320 |
from y | The y position of the start point | 180 |
to x | The x position of the endpoint | 319 |
to y | The y position of the endpoint | -179 |
fill list | The list you want to use as a container for the pathfinding result | list name |
prepross result | You have two ways to deal with the resulting data.
smooth: will remove the points between the start and end points of a straight line.
keep raw: keep the raw pixel by pixel pathfinding results. | smooth |
Normally you should choose to smooth the results, as shown below on the left, with the raw results on the right.
The list will be blank if the path cannot be found (no path is available between the two points).
Find the path between two sprites
This is a shortcut block. It does exactly as above, but you can simply choose two sprites.
Algorithm choice
You can choose the base path-finding algorithm implementation (JPS or A*), and the strategy used for each algorithm (faster or more accurate). JPS speeds are better than A* but slightly less accurate in most cases. When you choose a faster strategy (similar to the best-first algorithm), the path-finding result might not be the shortest one.
🚫 Obstacle
You don’t need to make an extra hit-box to test if the sprite can walk on a specific coordinate.
Is a coordinate on a map walkable?
If the given coordinate is a walkable area, it returns true.
You can also use this to test whether the current sprite’s target is on a walkable area.
Add a rectangle obstacle to a map
If you want to add a rectangle obstacle to a map, you can use this.
📝 Utils
Get the x-axis or y-axis value of a result item in a list
As you can see, the pathfinding result will be formatted in a specific format. [x,y]
In Scratch, you have to deal with a string operation to separate the x and y from the result.
Here are two utils for you to simplify the workflow.
If the first item on a list is [10,20]. The above code will extract the number 10 from the [10,20]. the code shown below will extract the number 20.
Set position to the sprite
This is a goto block, similar to the block goto x:( ) y: ( ). But you can use an expression to simplify the coordinate. It supports either (1,2) or [1,2] formats.
💬 Debug
To toggle the debug window, click the button shown on the left, and the debug window will be opened or closed as shown on the right.
Roadmap and Change Logs
Version | What’s New |
v1.2 | added:
1. Added the JPS path-finding algorithm, An optimized implementation of A* algorithm.
2. Use WebAssembly to implement JPS’s algorithm logic written in Rust (thank @-6 and @ob for providing algorithm support).
3. Bug fixes and performance enhancements.
Cappu at 21. Sep. 2022 |
v1.1 | added:
1. Added a rectangle obstacle to a map
2. Optimized map building algorithm (special thank @-6 and @ob for helping us to improve the algorithm)
Shawn at 12. Aug. 2022 |
v1.0 | added:
1. Totally new way to add obstacles to a map
2. Pathfinding and list filling
3. Debug tools
removed:
all blocks in version v0.1.
Shawn at 04. Aug. 2022 |
v0.1 | init launch
support customizable grid size and pathfinding |
