Pathfinding

bosswave

Anyone know of an efficient way to integrate pathfinding in a top-down game? It’s been my biggest roadblock in a couple of projects I’ve tried to create lol. Thanks!

Melide

@bosswave I've been searching for that too, couldn't find something simple enough. I saw a project of RobinsonX with a path finder systems, but I don't know if it would fit in all games ^^"

RobinsonX

I recently created a project that involves pathfinding and it works PERFECTLY! (Not the hyperPad one)

Unfortunately, it has been written in another language though. BUT, I can explain it.

RobinsonX

Here is the URL for a simulation of it. (Yes, it involves real-world code.)

https://py3.codeskulptor.org/#user305_LsWXuY7iAj_7.py

You can observe what is happening. (Works best on Computers)

RobinsonX

If I can find any time, I can update my path-finding project in hyperPad. (it's outdated)

RobinsonX

Alright, I'll try to explain it. (Sorry if this is too much.)

(Okay, it is too much...)

Here's a "simple" tutorial.

Have a grid of solid blocks and non-solid blocks.
Let Point A be the starting point and Point B be the destination.
When you want to find a path, perform these execution in order:

We will have blocks spreading from Point B. Let Growth Block be a function. Growth Block checks all of its side (up, right, bottom, left) and places a Growth Block for each adjacent non-solid block IF it has not been occupied previously with a Growth Block. After that, it sets a value, let's call it D, in it's place and whatever Growth Blocks it had just summon will set a value of D + 1 instead of D alone. So the D value from the destination should be smaller than the values further from it and vice versa.
Starting from Point B, have blocks spread from it. Point B executes a Growth Block in it's place. D should be initially set to 0, but any number would theoretically work. Notice that Growth Block starts a chain reaction where a single block clones into more blocks and covers the whole grid.
After the Growth Block has stopped executing, or when the spreading stops, and the starting point has not come in contact with any growth block, then there is no possible path.
Otherwise, if the starting point has come contact with Growth Block, then there is at least one possible path.

— We are only just NOW finding a path —

From the starting point, trace a path from the adjacent D values given. Let's have an object, calling it Bob. You can do this by checking the current D value where Bob is.
Bob will check the surrounding blocks and will move in the direction where D is less than the D value at Bob. In other words, Bob is moving towards blocks with smaller D values.
Bob will repeat this process of looking and moving until the destination has been met.

After a path has been found, you can make whatever character or object follow that path. The path that Bob took can be recorded in an array, a list of directions telling how to get to the destination.
If for some reason, the environment changes, like having a block added or removed, the process shall be repeated. (Or not, it depends on the situation.)

RobinsonX

This is what you should see. (It won't let me place blocks on Mobile.)
https://py3.codeskulptor.org/#user305_LsWXuY7iAj_7.py

SIRD4SH

@RobinsonX that... actually helps a lot. Thanks!

Now let’s just see if I can replicate this lol.

Edit: sorry, I keep forgetting to change the account on my phone.

SplitMindGaming

Hyperpad writes to cocos2d which actually has a bunch of tutorials on pathfinding. Im pretty sure it can be possible with hyperpad if new behaviors are introduced to support it.

Murtaza

We actually have a tutorial on a basic path finding system
https://hyperpad.zendesk.com/hc/en-us/articles/360031030412-Grid-based-Path-Finding

bosswave

@Murtaza thanks, I’ll definitely take a look at it!