# ShaX

Member Since 01 Nov 2003
Offline Last Active Apr 24 2012 08:30 PM

### Dijkstra Pathfinding Algorithm.

06 April 2008 - 05:13 AM

Firstly, if you don't know what pathfinding is, this script may not be for you.

If you do, then the first thing I would like to use to explain the script is the Dijkstra Algorithm.

Wiki: Dijkstra's Algorithm

I implemented the algorithm into a pathfinding function. It's very confusing to understand and I'm open to any tips to make it simpler or more efficient. I'm getting a headache just trying to think of a way to explain it, so here goes my best shot...

argument0: xstart. The x-location in our grid we start finding paths from
argument1: ystart. The y-location etc.
argument2: steps. The number of 'steps' away from the xstart and ystart we check.

This function reads from the variable from pathsteps[tile2[x,y]]. So tile2[x,y] is where you store the tile types of your pathing grid, and pathsteps[] is where you store how many 'steps' are used for that type of tile.
You need to set the two variables beforehand. So for example.
```pathsteps[0]=1 //it costs one step to move over tile type 0.
pathsteps[1]=2 //it costs two steps to move over tile type 1.
for (a=0;a<64;a+=1)
{for (b=0;b<64;b+=1)
{tile2[a,b]=choose(0,1)}} //make our grid.  Each tile is either type 0 or type 1.
w=64;h=64;```
(It also reads the variables w and h, the width and height of tile2.)

The script stores data about each tile in the pathing grid. They are as follows.
distance[x,y]: The distance you would need to travel from the xstart and ystart. It takes into consideration how many 'steps' are used on each tile (from pathsteps[tile2[x,y]]). Initially very large so that the algorithm can minimize it.
visited[x,y]: This variable can be ignored, it is used to 'spread' the paths every loop. Initially false, unless its the xstart and ystart, then it is true (it spreads from the start).
previousx[x,y] or previousy[x,y]: The coordinates of the previous tile, according to 'this' tile. In other words, where you would come from to get to 'this' tile. Initially -1 for all tiles.
canmove[x,y]: simple true/false stating if the tile is more than argument2 away from the xstart and ystart. If the distance is less than argument2, its true. If not false. Initially false.

The variables __xshift and __yshift were at one time temp variables but are now used for finding a path.

```//dijkstra(x,y,steps)
//variables required: tile2[x,y], w, h, pathsteps[z]

//var __xshift,__yshift;
//var visits,visitsprevious;
__xshift=argument0-argument2
__yshift=argument1-argument2

for (a=0;a<=argument2*2;a+=1)
{for (b=0;b<=argument2*2;b+=1)
{
if a+__xshift<0 or b+__yshift<0 or a+__xshift>w-1 or b+__yshift>h-1 {} else {
distance[a,b]=argument2+1
visited[a,b]=0
previousx[a,b]=-1
previousy[a,b]=-1
canmove[a,b]=0
spd[a,b]=pathsteps[tile2[__xshift+a,__yshift+b]]
}}}

visited[argument2,argument2]=1
distance[argument2,argument2]=0
stopper=0
visitsprevious=0
do
{visits=0;stopper+=1
for (a=1;a<argument2*2;a+=1)
{for (b=1;b<argument2*2;b+=1)
{if a+__xshift<0 or b+__yshift<0 or a+__xshift>w-1 or b+__yshift>h-1 {visits+=1} else {
if visited[a,b]=1
{visits+=1
if a+__xshift<w-1 {visited[a+1,b]=1;
if distance[a+1,b]>distance[a,b]+pathsteps[tile2[__xshift+a+1,__yshift+b]] {
previousx[a+1,b]=a;previousy[a+1,b]=b;distance[a+1,b]=distance[a,b]+pathsteps[tile2[__xshift+a+1,__yshift+b]]}}
if b+__yshift<h-1 {visited[a,b+1]=1;
if distance[a,b+1]>distance[a,b]+pathsteps[tile2[__xshift+a,__yshift+b+1]] {
previousx[a,b+1]=a;previousy[a,b+1]=b;distance[a,b+1]=distance[a,b]+pathsteps[tile2[__xshift+a,__yshift+b+1]]}}
if a+__xshift>0 {visited[a-1,b]=1;
if distance[a-1,b]>distance[a,b]+pathsteps[tile2[__xshift+a-1,__yshift+b]] {
previousx[a-1,b]=a;previousy[a-1,b]=b;distance[a-1,b]=distance[a,b]+pathsteps[tile2[__xshift+a-1,__yshift+b]]}}
if b+__yshift>0 {visited[a,b-1]=1
if distance[a,b-1]>distance[a,b]+pathsteps[tile2[__xshift+a,__yshift+b-1]] {
previousx[a,b-1]=a;previousy[a,b-1]=b;distance[a,b-1]=distance[a,b]+pathsteps[tile2[__xshift+a,__yshift+b-1]]}}
}
}}
}
visitsprevious2=visitsprevious
visitsprevious=visits
}
until (visitsprevious2=visitsprevious or stopper>300)

for (a=0;a<=argument2*2;a+=1)
{for (b=0;b<=argument2*2;b+=1)
{if a+__xshift<0 or b+__yshift<0 or a+__xshift>w-1 or b+__yshift>h-1 {} else {
if distance[a,b]<=argument2 {canmove[a,b]=1;instance_create((a+__xshift)*32,(b+__yshift)*32,o_canmovehere)} else {canmove[a,b]=0}}}}```

Translation of the code into english:
1. Go through our grid and store all the initial grid values.
2. Then set the values for the xstart and ystart.
3. Run through a loop that
(A:) checks the grid for 'visited' tiles.
(B:) If a visited tile is found, branch out to the left, above, right, and below, flag those tiles as visited, set their distance to 'this' tile's distance + that tile's number of steps, set that tile's previous x and y to 'this' tile's x and y. (B) is skipped if that tile's distance is already less than 'this' tile's distanc3 + that tile's number of steps.
(C:) checks how many tiles have been visited. If it is the same as the last check it stops the loop. (Also added a manual stopper to prevent an accidental infinite loop)
4. Goes through all the tiles and checks if their distance is less than argument2. If it is canmove[x,y] is set to 1. If not it stays 0.

The script checks if the tile that we are finding a path for is outside of tile2[x,y]'s limits (is negative or is over w or h). If it is it skips calculations for that tile.

It is very inefficient compared to A*. But it is an alternative. And with this pathfinding, not every tile has the same movement cost.

I know its very complicated and I will have an example up as soon as possible. If you have any questions before then feel free to post them.

### Hols

01 March 2008 - 05:12 AM

Hols
Hols is a simple and short puzzle game where the objective is to match rows of colored balls in holes to complete the levels.  The rules are simple but you have to plan your placements in order to win.
The game runs in 640x480 windowed mode.  It was made in GM7.

Screenshots

YoYo Games

Thanks for playing!

### Golf!

31 January 2008 - 07:59 AM

Hey everybody!

I'd like you all to try out my newest creation, Golf!  The game is based on the great pastime of hitting small white balls with clubs long distances.  However, this may be a little different from most golf games.  In most, you would be looking down at the golf course.  But in this game you have to play from the side!
You'll be fighting gravity, wind, and friction in your efforts to get your golf ball into the hole.  The game uses real physics to simulate bounciness and rolling.  Credit goes to Steffen_Itterheim for the porting of Open Dynamics Engine to GM through GM_ODE.dll.  He hasn't been seen in years, and his sight is nowhere to be found, but his DLL is still a great physics simulator!  If you want a source file of the .dll just let me know.

And now, the screenshots!

The title screen.  The game has a very cartoony design with thick lines and vivid colors.

The course designer!  I've created a fully functional and easy to use level designer for the game.  With a few clicks you've got a ready-to-play golf course!

Oops!  Golf! takes some time to master, even though the controls are very simple:

When the golf ball is still, click and hold the right mouse button to hit the ball.
Every time you hit the ball, it counts as a stroke.  (Even if it only moves an inch!)
If your ball lands in the water, you get penalized a stroke.  (Your ball is placed back at where you swung.)

The editor uses a system that can save multiple holes into a single 'course'.  To play a course, you choose it by clicking on the 'Tournament' flier on the title screen.

As of the current build, there are some issues with arranging multiple holes into a course.  Don't worry, they're getting fixed.

In the future:
-Backspin/forward spin shots.
-More types of terrain.
-Interactive course hazards.

Enjoy!
Oh, and it is made in   .

### Mazewar

07 January 2008 - 10:23 PM

Mazewar
P^3 Games

Mazewar is a classic first person shooter that takes advantage of Game Maker's direct3d capabilities to create a fast-paced arena skirmish.
Beta II Contains the gameplay engine with nonadjustable player and level settings.  There is a lot to come in the future in terms of flexibility, objectives, and much more.

These screenshots don't do the game any good, you really have to play it in order to see the potential.

Thanks for playing!

### Marble Combat

08 July 2006 - 06:40 PM

Marble Combat

MC was a game created by a group of friends that loved to play fighting games against one another.  Through the implementation of realistic physics and ragdoll motion, the game has become an exciting game for two players that has remained fun to us for over three months now.
The game uses GM_ODE, the open dynamics engine ported by Steffen Itterheim(s?).  A link can be found in the sticky on the Extending Game Maker section of the forums.
Before downloading, keep in mind this is a two player only game.  One player alone can toy around with the physics if you desire to do so.
Unfortunately, the source for MC has been lost in an emergency schoolwide computer wipe.  While the version I will link is not the final, it is very close.
I hope you enjoy this game with your friends as much as I did with mine.

Controls
The red player uses the arrow keys, and the blue player uses the WASD keys.
Left and right (A and D respectively) spin your character, and Up (W) is used for "floating" -- while floating, you consume fuel which is shown in your respective corner of the screen, so use it wisely and when necessary.
Next to each player's fuel is a score keeper.  Every time you throw the enemy player into the bottom of the stage, you gain a point.
At the top of the screen is a timer.  When the timer reaches zero, a draw is called and noone scores a point.  The score is only reset when the game is restarted.
Remember, grabbing onto your enemy is the key in this game!

This game changes your resolution to 1024x768, fullscreen mode.

]