Grid Based Pathfinding from Cell to Cell

[GMPanda]

Hello,

Another newbie here.
I am beginning to work on a top-down view RPG style adventure game. I am looking for a solution so that my Player character will move using Pathfinding behavior. Additionally, the player must strictly adhere to grid-based movement traveling from one cell to another. As usual, due to the pathfinding behavior, the obstacles (kept in certain cells) will be avoided.

In other words, when the mouse is clicked in one of the cell, the destination must always be rounded off at the CENTER of that cell, thus the Pathfinder must consider this center point as destination and the player should travel to that point.
The grid doesn’t need to be visible.
I am not all good at Math or Logic, so I am kinda stuck even after referring at the examples provided within Gdevelop.
I would really appreciate if someone could guide me on to approach the logic for this. And also please suggest the appropriate Gdevelop expressions that need to be used for this.
I am not even sure if the method discussed above would be the best way to get the desired effect. Alternate solutions are welcome.Thanks in advance!

P.S. I am not looking for snapping effect. The Player has to walk from one cell to (say) a far away cell.

[Gruk]

Hi,
Did you try those actions?

Where are you actually stuck?

[GMPanda]

Hi,

Thanks for reply.
Well yeah, when I say ‘Stuck’ I mean I don’t know where to begin.
I have looked into Height of the cells, Width of the cells.
Its just that I don’t know how to use them. If I could use them to calculate the center of a cell (the cell where the mouse was clicked), then its a problem solved.
Are there any examples that I can see to better understand Virtual Grid?

Further I will illustrate my requirement:

[reina]

I see these important highlights, and will try to answer them:
“when the mouse is clicked in one of the cell, the destination must always be rounded off at the CENTER of that cell”
Firstly, let’s clarify that the coordinate of an object is at the top left of the object; In your picture example in your second post, assuming the grid is 20 pixels size, the player sprite’s X position is 40 and Y position is 60. Or, the player is 4 squares down and 3 squares right (if that makes sense). This means that to make sure the player object is centered in a grid, we need to make it align with the top left point of each tile.
From this: Basic game making concepts: What you need to know to start with GDevelop [GDevelop wiki]

Do you know how to use pathfinding with mouse? The pathfinding example is a good basic.
Once you can implement that, we’ll use Modulus (essentially, the remainder of a division) to round off the coordinate the player should move to. To do that we first need to store the value of MouseX() and MouseY() to store the mouse coordinates into two variables, let’s call them CoordinateX and CoordinateY.
Then, subtract mod(CoordinateX, 20) from CoordinateX, and same with CoordinateY. This should, for example, if player clicked on X position of 56, subtract it by 16, then getting 40.

As for actual grid setting of pathfinding, enabling GDevelop scene editor grid may help you. It’s this icon:

Enable “Show grid”, then change Setup grid X and Y cell size. This grid is visual only, dies not affect Pathfinding, but it’s easier to work your grid system. It also snaps when you drag objects, if you don’t want that hold Alt while dragging.
We’ll use this same cell size in a bit.
Then, open “Edit Object” for your player object, then go to Pathfinding behaviour. Scroll down to the bottom.

What was the value you set up for your scene editor grid earlier? 40 for X and Y? 80? Set it to the same value as earlier. When you develop levels the object placement and Pathfinding can work with each other.

I hope that helps, if you need help on a part feel free to reply.

[GMPanda]

Hi cat,
I was hoping you would join the discussion. I appreciate your help.

The part I didn’t understand was:

"Then, subtract mod(CoordinateX, 20) from CoordinateX, and same with CoordinateY. This should, for example, if player clicked on X position of 56, subtract it by 16, then getting 40."

I am not too good with Math, my understanding(or misunderstanding) of the term ‘Modulus’ has something to do with sign (plus or minus?) So, it confuses me even more. Which is why I used the term “round” in my explanation, but I only came up with it by observing the Gdevelop example “snap-object-to-grid”. To be honest I didn’t understand the expressions used in this example at all. It uses ‘round’ to somehow calculate the cell. Anyways…

It was this Gdevelop example and the other one called “center-object-within another” , and to somehow implement the combination of both to come up with a solution. But it only led to more confusion as I am not able to figure out how it would fit in pathfinding/grid.

Another thought that came to me :

I was experimenting with the example “center-object-within another” and it had the expressions like,

For Brick :
MouseX("",0)-70/2
MouseY("",0)-70/2

For Coin:
MouseX("",0)-36/2
MouseY("",0)-36/2

For Collision of Brick and Coin:
Brick.X()+36/2
Brick.Y()+36/2

Note: the brick is 70x70 and coin is 36x36

So, I went ahead and edited (moved) the origin points of both objects such that they align with their centers (35 for brick and 18 for coin).

Next I modified the expressions to simpler forms such that

For Brick :
MouseX("",0)
MouseY("",0)

For Coin:
MouseX("",0)
MouseY("",0)

For Collision of Brick and Coin:
Brick.X()
Brick.Y()

…and the game ran the same way without any problems.

My point is …can we simplify things by editing the origin point? …is that even a good idea to modify origin? coz my concern is that once origin is modified other issues may arise when the game gets complicated?

Its just a thought.

I understood the rest of your solution, but I am almost always stuck when it comes to Math expressions while observing Gdevelop examples and various other solutions at forum.

Awaiting your response further. Thanks.

[Gruk]

Editing the origin point is not a problem, it will only offset the instances visible on the scene editor.

[reina]

Hmm, like Gruk said, it’s fine to modify origin points, but you’ll have to modify the formulas I gave too (I haven’t tried, though). Otherwise the player object will move into the edge of a grid instead for example - then, you might need to change origin of grid object also.

For round(int), looking at the expressions reference,
I assume it rounds up or down the number if it has decimals, like this: (Math.round(2.5) equals 3)

Then, I looked at the snap-object example…

There’s two things happening here, cell_width variable is divided with the result of the round(). In this round(), the pea’s current X position is being divided with cell_width variable, which is 32. I’ll show an image of the grid, each yellow text represents what X and Y position they are. In this pic, the green pea is centered at 64, 64. The origin of the pea is at top left.

When the pea is dragged, it snaps itself based on where the top left of the pea position currently is.
It might help you understand if we make the current pea position visible. To do that, create an event above the drag event, modifying the text with this:

With this, you can see pea’s X and Y position, and when you release pea you will see the position once it has snapped. You will notice that the snapped position is either higher or lower than when you were dragging the pea.
You might also understand the position concept better by disabling the snap event altogether.

For modulus, well… After looking through the above pea example, if you understand that, you can use that round() system.
Otherwise, in my previous post, mod(56, 20) means 56 divided by 20, can be divided 2 times, then there is a remainder of 16. We subtract the earlier MouseX() with this 16 so it will snap to the grid top left position.
If that still confuses you, I’m afraid you may need to google or youtube learning resources about the topic on your own… Or refer to the pea example if you can understand it.

Hope that helps!

[GMPanda]

Okay,I think I starting to get this now, and I understood both your solutions. Thanks to the detailed explanation. Let me try these out and experiment. I’ll check back once I have something.

[GMPanda]

Ok guys, before I get deep into cat’s solutions, which is obviously the efficient way in the long run, here is what I have got using an alternate way. Think of it as a poor man’s code

It may not be the most efficient way (not at all) of doing this, but it is getting the job done for now to an extent, so that I can at least kick start my project. There is one problem I am facing with this now which I’ll discuss in a bit.

So basically my goal was to try this out with least code as possible. Based on earlier suggestions by Gruk, cat and some other examples, this is the result of me struggling hard with coding. even if its a simple one. This took me an entire day, is the testimony of my kindergarten level of Math and Logic.

So here is a screenshot of my humble scene events.

I am attaching the scene file here : https://drive.google.com/file/d/187GtqNI7Iv1l5xgAzPu48SsWWeQ1t4Nk/view?usp=sharing

Situation:
First as per you guy’s suggestion I looked into virtual grid, how to enable it, setting it up and so on.
So I set the virtual grid-size (in pathfinding behavior) to 64x64 and basically all sprites in the game is also set to 64x64.
I have two main sprites namely ‘Blob’ as the Player Character and ‘EmptyTile’ for other use which I’ll discuss in a bit.

If you take a look at the events code, and run the game , the result is pretty much what I wanted. Basically, the pathfinding is single handedly taking care of it pretty well.

Now there is the issue. As you can see, I have setup a ‘highlight’ animation for empty tile sprite. This lights up when the mouse is clicked on a cell. But in the game if you observe, if we keep clicking, then after 20-25 times (randomly) the highlight animation stops working, then after a while it works again for a few clicks and then randomly stops again.

I do not understand why this is happening. (a memory issue of some kind?)

Perhaps reason is the inefficient way I have implemented the ‘EmptyTiles’.

You see, I have manually laid a number of ‘EmptyTile’ instances on the Scene Frame, one for each cell of the grid.
Where ever the mouse is clicked the highlight animation of that particular instance of EmptyTile is triggered. But it is facing this issue that I have discussed.

So what could be the issue here? Any ideas?

P.S. I must reveal my overall goal. I am trying to develop a game that has similar mechanics to the mobile game - “Stranger Things”. It has been done in retro style. Here is a gameplay link. Please observe the way player movement has been implemented. Stranger Things: The Game (Android Gameplay) - YouTube

[reina]

Well, wow! It’s so simple, I’m not sure how it even works. MouseX() captures current mouse position, yet it’s snapping to the same grid.

About your problem, the logic checks out, I’ve no idea why it wouldn’t work.
I fixed it by duplicating the tile object to be a serparate cursor named AnimTile, and removed the first blank animation.
Then, I created one AnimTile at the top left of the window (0,0) and set it to last frame so it would be the blank frame.
So, when it’s clicked, I put the whole MouseX() - mod(MouseX(), 64) stuff to snap it to a grid. Then, restart the animation (set frame to 0) and play it again.

That probably sounds confusing, but I don’t know how else to fix your problem to be honest.

[GMPanda]

Well it was a total fluke on my part, I was only trying using bits of info that you guys were giving (only the bits that I understood )

But why it works is perhaps it may have something to do with the grid cell size and sprite size being the same (64).

Now for the issue that you just solved. That’s what I would call an efficient way to implement the AnimTile. Now I can get rid of those redundant instances of EmptyTile!

I tested your code and it works! Creating a single AnimTile and then moving it around at every click is totally efficient and makes sense.

I am already learning so much through this discussion. Thanks a lot guys!

cat, I must recommend that you should totally start a Youtube channel that teaches Gdevelop, coz you are really good at this. There is some serious shortage of good Gdevelop tutorials on Youtube.
smiley_cat:

[reina]

Thanks! I’ll think about it. Lately I haven’t been putting much energy into GDevelop stuff, your topic is the only one I replied to this week.

Your EmptyTile totally works as a movement scheme alone, but yeah, lesser objects in a scene is a good thing. And great job for understanding how the weird MouseX() - mod(MouseX(), 64) formula works!

[GMPanda]

Hey Guys,
Now on to next issue that I observed.

The game that I am referring to, ‘Stranger Things’ doesn’t have this issue. Stranger Things: The Game (Android Gameplay) - YouTube

Any ideas, how to achieve this?

[reina]

Hey again,
The simplest way to fix this issue is to use an action called “Separate two objects” event (not sure why Pathfinding acts like that).
Create a condition first to check if Blob is colliding with Wall, and then use that Separate two objects event (the Blob should move).

[GMPanda]

Hi there,

Had already read up on ‘seperate two objects’ but used only after you suggested.
The result was…well let’s say a tug of war between 'pathfinding, and ‘seperate two objects’

Both of these want to work the way they should but the net result is such that the moment Blob reaches the corner wall it basically still cuts the corner as before but due to the effect of ‘seperate two objects’ the Blob simply disappears at that point and then spawns at the other end of the corner.

In other words , all those frame are skipped which are supposed to show the ‘cutting the corner part’.

Edit: I havnt put any condition for the event ‘seperate two objects’

[GMPanda]

I found this in reference to UNITY, seems like its a lot of code for me
https://forum.unity.com/threads/avoid-cutting-corners-with-diagonal-movement-pathfinding.405408/

I googled ‘cutting corner problem in pathfinding’ it appears its a common issue and takes fairly advanced and complex solutions.

[Gruk]

You might want to consider making your obstacles hitboxes bigger than the sprites, to keep a safety distance?

[GMPanda]

Hi Gruk,
Making the hitbox bigger than the sprite is perhaps not possible? I gave it a shot. We can go smaller but not bigger.

[GMPanda]

Found a bunch of Expressions at Wiki.

can these be somehow used to develop a logic that can avoid corner cutting, while keeping the Diagonal movement ‘On’?

|Expression| Description||
|Object.Pathfinding::GetNodeX(number)|Get next waypoint X position|
|number|Node index (start at 0!)|
|Object.Pathfinding::GetNodeY(number)|Get next waypoint Y position|
|number|Node index (start at 0!)|
|Object.Pathfinding::LastNodeX()|Last waypoint X position|
|Object.Pathfinding::LastNodeY()|Last waypoint Y position|
|Object.Pathfinding::NextNodeIndex()|Get the index of the next waypoint to reach|
|Object.Pathfinding::NextNodeX()|Get next waypoint X position|
|Object.Pathfinding::NextNodeY()|Get next waypoint Y position|
|Object.Pathfinding::NodeCount()|Get the number of waypoints on the path|

[Gruk]

If you resize the player sprite without rescaling it, it should give you some room for a larger hitbox.
Not sure if you can avoid cutting corners by manipulating the waypoints, sounds like a good candidate for free headache