#### Ariak

##### Member

**GM Version**: 1.4.1575

**Target Platform**: ALL

**Download**:

**Links**: Pastebin http://pastebin.com/dxJjsptD

**Summary**:

This tutorial will feature a couple of scripts that will enable you to work with 45° slopes in GameMaker without using any wall objects – entirely based on grids. Additionally there will be

**terribly**drawn visual explanations.

- Checking a single point (x,y) for a collision vs a 45° triangle in a grid_cell
- collision line checking between two points
- 2D top-down 45° slope movement code, including subpixels, and angular adjustment

**Tutorial**:

Hey,

thanks for your interest in this tutorial. Sadly the massive text I wrote for this got scrapped by the forums character limit. Use the GMZ with commented code, and maybe the pictures will help too.

**A few things to note first:**

- Try the demo project first to see what’s being worked on. Use the visualization button (b) and Zoom (x) to get a closer look at what is going on and how the collision checks are done. Press space to delete all the invisible objects to see the performance boost (instance counter bot left corner).
- If you cant run the .gmz file with the YYC or its just to slow going for your machine, adjust the roomsize to 3200x3200 px and test again. You will still see a good perfomance boost without objects (press Spacebar)
- Go check out Heartbeast Tutorial called "Random Level Generation [P2] Grid Collision" -it helps understanding my tutorial alot.
- Cell Dimensions are a fixed 32x32. For simplicity and readibility there is no cell dimension macro variable.
- The player is a 32x32 object, thus exactly the same as the cell. See comments below on how to adapt this to a 16x16 player object.

- Yes, its unusual to have the grid stored in player object - hes not designed to die.

- This tutorial is for 45° slopes only, especially the 2D top-down movement code. Some of the other elements, like the collision_line or collision_point code may work for any form of shape/slope – depending on your adaptations.
- sx,sy,tx,ty stand for start x, start y, target x, target y
- There is no one size fits all solution, I've limited it to 8 directional movement for now. More is definetly possible!

**Essential function :**&~31 returns the nearest value evenly dividable by 32: 99&~31=96.

Some people might not know this and get stuck in the gmz file.

So why use a grid and not wall-objects, since they can do precise slopes!?

So why use a grid and not wall-objects, since they can do precise slopes!?

Because using wall objects causes major perfomance headaches. Especially since you will most likely need Game Makers precise sprite collision checking activated if you want slopes.

Using grids is tons more efficient, as there are no wall objects that constantly update their built-in variables.

With the following pictures n thoughts i'd like to demonstrate that there is a viable alternative.

**/// ==========================================================**

PART 1: Checking if a single point (x,y) collides with a 45° triangle in a grid cell.

/// ==========================================================

PART 1: Checking if a single point (x,y) collides with a 45° triangle in a grid cell.

/// ==========================================================

The linear equation for the hypotenuse of a triangle of 45° is given by y(x)=x. Thus the above picture shows how we can check collisions using a simple boolean check, which returns either 1 for true, so a collision did occur, or 0 for false - no collision. We will only need remainders (mod) of a given x,y value pair to determine collision, and the div function to reference the grid.

**NOTE:**

In Game maker there is a among other similar functions one called point_in_triangle which does the same thing, but it needs a lot more coordinates. See GML: Collision Checking Without Masks. https://docs.yoyogames.com/source/dadiospice/002_reference/movement and collisions/collisions/index.html

**/// ==========================================================**

PART 2: Collision Line

/// ==========================================================

PART 2: Collision Line

/// ==========================================================

We will need to check 2 points per cell, which represent the borders - see visuals provided!

- The start point (sx,sy) and its nearest respective boundary with the grid - x can be 0, or 31 and y can be 0 or 31 to get the cell borders. See the picture on the points above for this. So 2 checks for the start cell
- The end point (tx,ty) and alike to the start function, its nearest boundary intersect along the line. Same as above, 2 checks for the target cell.
- and 2 checks for all the grid cells that the line crosses between (sx,sy) and (tx,ty).

- Only one intersection is present if the line either
*just*touches the corners, or either the start or end point fall within the cell. - There’s also the special case 0 where both start and end points are within the same cell.
- Furthermore another problem occurs if we use rounded values. If the angle is steep enough there is a possibility that multiple pixels actually intersect the border. See the picture below ,right hand side. Think of it as the pixel art vs anti aliasing which at least tries to be 'as correct' as possible.

To circumvent the rounded pixel problem (right hand side depiction), I determined the intersections mathematically, yielding subpixel perfect intersections, using the slope of the given equation line between two points.

The equation for 2 points along a line is given by y=mx+b. Assuming we know both (sx,sy) and (tx,ty) the slope m is determined by m=(delta y / delta x). We can use this to get a corresponding y value, for a given x. And vice-versa.

Right of the bat we can check whether both start or end points are in collision with the grid using our collision_point code. If they are, we're good and can break//exit already.

Otherwise we will split the task up into two components:

- incrementing x values to nearest cell boundary intersect and calculated corresponding Y - using +1 to enter the next cells adjacent border, and +32 from the same point to get to the opposite cell border.
- the same vice_versa for Y, and adjusted X values;

**/// ==========================================================**

PART 3: 2D Top-Down Movement Code, 45° Slopes and Angular Adjustment

/// ==========================================================

PART 3: 2D Top-Down Movement Code, 45° Slopes and Angular Adjustment

/// ==========================================================

Pixels vs subpixels: The movement will always be in full pixels to avoid sprite tearing. Decimals along an axis are cumulated until their sum is equal to or greater than 1. In which case 1 is added to the next speed input along the given axis, and the counter starts anew. To avoid janky movement along slopes there is one extra OPTIONAL line in the code for the X axis check. It will limit the speed along y axis to that of the x axis to create perfect 45°, regardless of whether that little decimal +1 just kicked in for y - which would cause the janky movement. It’s not necessary to do the same for y, as it runs after the x checks.

Disclaimer: Due to the nature of the angular adjustments to the nearest integer (=> full pixel value) the movement will feel off for speeds that are below 3px per step @ 60 fps. Its either that or sprite tearing.

**Please Scroll Down to McWolke's comment. There is a minor mistake in the movement code (movement in combined direction) that leads to shaky movement (most noticeable at lower speeds).**

EDIT:

EDIT:

The base logic is to first check if there’s a collision ahead along both x,y axis simultaneously. If not, we can skip …. everything. With one exception, we need to manually slow down our movement speeds if we’re moving at an angle. Otherwise moving along any angle will always be faster then moving along on a 90°, 180° etc angle. The distance covered by x+1,y+1 is not 1, but 1.4… . Thus to preserve a natural speed we adjust the x,y vectors.

Now assume that the combined collision check returns there is a collision. We will now need to seperatly check both axis as the the direct way forwards is blocked. The principle for the slope movement is depicted below. The picture in the middle shows how the direction choice is being made: up and down are being checked, the return value is then the new direction. This is similar to how a sign function would essentially work. It can be -1 for up, 0 for no decision (both spots collide), and 1 for down. See commented code for details.

If you want this top down movement code to work with objects you will need precise collision checking enabled. Next, simply replace ‘gridcol_place_meeting’ with GM's standard ‘place_meeting’ and your object to check against. Done!

**So how does the gridcol_place_meeting function look like, and why can't we simple use gridcol_point from Part 1?**

The gridcol_place_meeting works in a very similar fashion to what Heartbeast demonstrated in his grid collision tutorial. We determine the 4 corners of the sprite with the grid. Only checking the sprite origin point is not enough. You would be able to move halfway through walls.

Gridcol_quadrant_rectangle performs the actual collision check, for each of the 4 points specified by gridcol_place_meeting. As we are using slopes we need to check even more points then just the 4 corners - see left side picture below, where the player can enter the triangle if only its 4 corner points are checked with gridcol_point. The problem is that the character is a rectangle, not just 4 indivual corners, it has edges. To solve this issue the gridcol_quadrant_rectangle function will additionally require the sprite origin. It uses this to determine max 3 collision points per cell (=> quadrant) - see middle pixture below. So per cell the target value and the respective nearest intersections with the grid. It can now detect whether there is a triangle in the way - picture on the right. The actual collision checks now follow the same principle as gridcol_point, but we those extra points. If the character is boxed in on all 4 sides by a slope 12 point checks are performed. 3 for each slope.

Visual representation helps! Notice how you can enter the triangle, if you only check the corner points? That’s why the extra points "in the middle" are added by the quadrant_collision. They check the points aligning with the grid. See visual representation in the demo and use the zoom to see how they behave. Although all 12 points are always shown in the demo (they can overlap to "hide") , if the cell is free or a square wall only one point, the corner point, is checked for efficiency.

**/// ==========================================================**

Final Thoughts

/// ==========================================================

Final Thoughts

/// ==========================================================

I hope this tutorial helped you - i certainly wracked my brains coming up with the collision line code.

In my tests it was alot more efficient to use my collision line versus the standard while loop, sx+=lengthdir and a step counter method. With a step size of 5 my code was 3-4x faster. Additionally the brute force method is also inaccurate due to the nature of the step...! (see 'brute force' script in gmz file)

The walls are visually represented as tiles in my demo. If you want your room to appear even larger than 6400x6400 you will need to think about drawing the tiles to a surface instead to 'fake it' - its the method that Rujik is using in his 'Pale Meridian [Action RPG]', his room is actually tiny. But the world appears friggin huge - see his post in the 'Work in Progress Section'. I tested running the demo in 32000x32000 (with objects previously disabled). It took forever to load, but it runs at around 250fps , quite similar to the performance of the demo rooms 6400x6400 with objects. [FPS value based on my end.]

There is a wonderful script of nested if statements by Nocturne for Autotiling - srsly... hats off. Which is demoed by Shaun in one of his tutorial videos. The script can easily be adapted to work with a grid, instead of wall objects. I even managed to modify it to factor in slope tiling. Im mentioning this, because it would be the next logical step when you think about game world creation.

Happy coding.

Last edited: