How do I do Custom Pathfinder for Hex Maps

I'm thinking in make a game using hex maps, and after researching a bit found the support for Hex maps on Tiled.

Now I'm whiling to learn how to make this custom pathfinder system to use with the map: http://forum.mapeditor.org/t/support-fo ... s-added/47

It will have terrains costing more to move over, also, it will be jagged like this:

So, anyone already did a system like this? and can share?

Thank you =]

Telles0808;

Rex Rainbow has an addon that does hex maps with pathfind. Not sure its exactly what you want, but take a look.

yours

Winkr7

It's very nice to know, but I'm looking for the logic behind it, because using plugins will take my control over it.

Cheers!

TELLES0808

well, kinda depends on how your game will work, are you building a two (or more) player game and want to show/highlight possible moves, or suggest the best possible move? give a hint? Or have a player play against the computer and build an AI that will be able to play the game by itself?

the logic would go something like:

specify a start block (and possibly a target block) - then if you are rolling dice, calculate all possible moves and the benefit of each move, sort them and pick the best move. Or if it is just a matter of deciding how far you can move for a specific cost, or how far you can move without making units vulnerable, then factor that into the cost/benefit of each possible move, collect the results in an array as they are calculated, sort and pick the move with the best result.

A human can glance at a board like that and rule out most of the inefficient moves instantly. A computer needs to brute force calculate every move to know what to do.

Good point.

The game will be about Pirates and Corsairs.

The board will have ocean, with dangerous environments, also, when the wind is counter the player path, will cost more to move.

My main problem was not the human part itself, but about the logic to start making an AI good enough to chase, run away, hide itself, and take advantage routes while engaged in battle.

Its pretty much the same as isometric:

http://clintbellanger.net/articles/isometric_math/

Just think of the hexagons as iso cubes.

The offset should be equal in size.

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.

Thank you newt, I think these logics are pretty nice.

The author is very similar to my brother in appearance, lol.

R0J0hound, Thank you for the sample, really appreciated! The sample CAPX is perfect!

The images above are using the corner to show the sample because they are from the Tiled site, this is just a random image.

The results of studies will determine if the game will be turn based, timed in lots or real time. I'm worried about the usage of CPU when dealing with 4 ships at the same time, for example.

R0J0hound - wow, that is an awesome capx example!

TELLES0808 - CPU usage is actually quite low the way it is now (not many tiles, and it randomly chooses a goal rather than trying to find an optimum goal based other game factors). My iPhone ran it for over an hour (at 60 fps) without getting warm - and usually just about any game makes it get warm pretty fast. On my PC, cpu utilization was around 10% (after I made it wait for me choose a move it dropped to 5%.) So, I think it should scale to bigger maps with more pieces nicely.

while my phone was happily running it I was playing with the capx on my computer - I made it wait for you to click on a tile to move to, and had it display how many steps that was, and what the total cost would be. I also added a tile that cost 10 to see how it handled more complex terrain configurations. (it handled it extremely well)

That was way more fun than what I should have been working on! : )

Hi AllanR, I noticed, thank you!

Here is a sample test of the very first alpha test of the game engine.

Don't expect too much, but thanks to R0J0, it's already working as expected.

In the next months I'll work in the AI and game aspects, to make more sprites later.

https://www.scirra.com/arcade/other-gam ... -test-1841

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.

The capx and a live sample is on arcade for download.

https://www.scirra.com/arcade/other-gam ... -test-1841

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 <img src="{SMILIES_PATH}/icon_e_biggrin.gif" alt=":D" title="Very Happy">

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

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.

Bravo n1 R0J0hound Thank you so much

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