How do I do Custom Pathfinder for Hex Maps

Get help using Construct 2

Post » Thu Aug 20, 2015 4:38 am

@allanr
@telles0808
I'm glad it was useful and amusing to tinker with. I had fun making it.

Concave terrain like that would cause the algorithm to run longer, but it's only an issue if pathfinding for all your ships ends up being too slow. A simple thing you could do is avoid concave terrain in your levels.

Or if you're feeling ambitious you could reference this fun site for other pathfinding ideas.
http://theory.stanford.edu/~amitp/GameProgramming/

One thing I've done in the past is calculate the path over multiple frames instead of all at once. It helped spread out the pause when a large amount of nodes were used.
B
94
S
33
G
117
Posts: 5,387
Reputation: 75,335

Post » Wed Nov 30, 2016 1:33 pm

The capx and a live sample is on arcade for download.
https://www.scirra.com/arcade/other-gam ... -test-1841
Image
B
108
S
24
G
18
Posts: 1,375
Reputation: 22,828

Post » Fri Oct 27, 2017 8:54 pm

R0J0hound wrote:Any reason for using a corner of the hexagons instead of their centers?

If done manually with events you'll use this for finding the path:
https://en.wikipedia.org/wiki/A*_search_algorithm
The difference between a hex grid and a rectangular grid is just how the neighboring grids are found. For simplicity collision detection can be used.

Here's an example:
https://www.dropbox.com/s/dwg8owxstf76g ... .capx?dl=1
/examples29/astar_hex.capx
In it it defines a function "astar", which you call with two iids: a start and and end node. After the function the start node's node.next will be the uid of the next node in the path. This can then be repeatedly followed to the end node. For smooth motion you'll have to use the moveto behavior or devise your own method.

Event #9 is where you control the cost to move to a node. Right now it uses the distance times the average of the node costs, but there's no reason you couldn't tweak it to be based on other factors.



Wow @R0J0hound that was awesome and is running amazingly fast, runs at 1 % in my Laptop :D

I was looking for some type of Pathfinder like this for a "Bomber Man" like Game which turns out is an incredible challenge the Ai, I try it to replicate your Capx to use it with Squares tiles and I got some troubles that I can't figure it out, I would love if you can give any advice if possible:

1-My first problem is that on this capx moves in diagonals swell but in Bomber Man only moves four directions (Up, Down, Left, Right) is there is any possibility that it doesn't count the diagonal moves? so it doesn't go through between two solids blocks

2-How would I make the same thing but for each Enemy? Example Each Enemy has to find his Path to the Player independently, will be possible to do this without Arrays?


3-I haven't touch much the official Pathfinder in c2, will it be better for a Game like this to use the official Pathfinder or what would you recommend with your experience?


I hope you can give me some guidance as I'm a bit stack here, thank you so much for your Time

This is what I got so far:
https://www.dropbox.com/s/zcww0mepocp26k3/FindPath1.capx?dl=0
B
41
S
25
G
87
Posts: 305
Reputation: 48,088

Post » Sat Oct 28, 2017 5:49 pm

@tarek2
1.
This was made for hex tiles specifically, but if you remove the events to set the scale (8 and 12), and make the nodes square with octagon collision polygons it should work. There other examples elsewhere using square tiles i think.

2.
I'm not sure it's suitable for multiple objects as is since the path found is stored in the nodes themselves. I guess one idea you could pursue is to store the path in an array after the path finding is done so that the nodes can be reused and the sprite has a list of moves.

3.
I haven't really used it. Plenty of people have used it for what you want to do so whatever you find works for you.
B
94
S
33
G
117
Posts: 5,387
Reputation: 75,335

Post » Sat Oct 28, 2017 7:25 pm

Bravo n1 @R0J0hound Thank you so much :D

The trick for "octagon collision polygons" than the trick perfectly it avoids diagonals now, I can't believe it was that easy I been trying it for a week to do this jeje


Thanks for your help I really appreciate it



There is one last question for anyone that can help on this, I know is gonna sound funny but I swear I cannot debug how is possible that picks each tile of the path plus highlight them because this is what I know

-The Function gets Call once to find the Path and is a trigger once
-The Function Runs top to bottom never goes back UP unless the Function gets called again if I'm not mistaken
-The Loop starts with one node that is "Open" & (Done =0 )then in the following subevents gets opacity 0 so far we have only one with opacity 0 & (Done =1 ) which stops the Loop, but how is possible that goes again back up to highlight the rest of the tiles of the path if the Function doesn't get call again?? I been trying to figure it out and I cant

-Also, Why do you need to Return the Value 0 or 1 at the end of the Function? because if I disable still works normally doesn't break anything


Thank you in advance
B
41
S
25
G
87
Posts: 305
Reputation: 48,088

Post » Sat Oct 28, 2017 8:55 pm

@tarek2
This would be a case where it would be nice if C2 allowed you to step though the code with the debugger. Anyways it may be helpful to read about the A* elsewhere to see how it works.

I use the 'done' variable to stop the looping. It's only set when the goal tile is reached. The reason it keeps looping even though it starts with only one object that's 'open' is the neighboring tiles are picked with a family and added to 'open'. To clarify node and othernode can refer to the same objects. Maybe that's where the confusion is.

The return value is not used in this particular example isn't used but in cases where a path can't be found 0 is returned. That can happen when trying to find a path to a separate island of nodes.
B
94
S
33
G
117
Posts: 5,387
Reputation: 75,335

Post » Sat Oct 28, 2017 9:37 pm

R0J0hound wrote:@tarek2
This would be a case where it would be nice if C2 allowed you to step though the code with the debugger. Anyways it may be helpful to read about the A* elsewhere to see how it works.

I use the 'done' variable to stop the looping. It's only set when the goal tile is reached. The reason it keeps looping even though it starts with only one object that's 'open' is the neighboring tiles are picked with a family and added to 'open'. To clarify node and othernode can refer to the same objects. Maybe that's where the confusion is.

The return value is not used in this particular example isn't used but in cases where a path can't be found 0 is returned. That can happen when trying to find a path to a separate island of nodes.



I see that makes more sense now, is gonna take me time to fully understand it through my brain is been spinning like crazy :D that is an awesome Loop man I need to learn that, I didn't know you can do that with a Function in one call

This would be a case where it would be nice if C2 allowed you to step though the code with the debugger.

That would be awesome would have saved me one week of debugging running in circles I tried all kind of tricks and no luck jeje

I will keep reading about A* like you said to learn more about it.

Thank so much R0J0hound for all your help

Take care
B
41
S
25
G
87
Posts: 305
Reputation: 48,088

Previous

Return to How do I....?

Who is online

Users browsing this forum: katzin and 9 guests