Hexagon pathfinding (or not)
Author
Hello,
while I am working on a hexagon-based strategy game quite similar to the old Battle Isle series (turn-based), I stumbled across a problem I am unable to solve on my own, so maybe you can guide me into the right direction...
I don't know how to resolve the pathfinding in general. You see, A* works well for RTS games where distance is no problem at all, but with a turn-based strategy game, I have to find all the possible tiles a unit can move onto, based on its basic movement speed/steps per turn.
I am not sure if "Isometric Game Programming" covers this problem as well, and the author's two articles on GameDev.net didn't help me much. I also checked out Amit's website, but without success.
The "dirty" way would be to check every tile that is in theoretical range (like there were no obstacles or unallowed tiles in between) using the A* algorithm, but I don't believe that's the best way to achieve this.
Thanks in advance!
Thomas
so you have 5 sides to a tile....and x tiles to the grid...
make a way point node mesh...give every tile a node, inside that node hold data such as whether or not its passible, etc. Now connect its node to each of the five nodes surrounding it...you can run A* on this...although a* is slow sometimes a djikstra works well...take the passability into consideration whilst working out the hueristics in your algorithm....
thats a basice concept but you should be able to implement it rather easily...you could make the search quicker(if your grid is small) if you pre store every possible path in a database and do a quick lookup as to ho to go from on to the next...
hope this helps, im sure there will be other ideas to follow from others...ciao
make a way point node mesh...give every tile a node, inside that node hold data such as whether or not its passible, etc. Now connect its node to each of the five nodes surrounding it...you can run A* on this...although a* is slow sometimes a djikstra works well...take the passability into consideration whilst working out the hueristics in your algorithm....
thats a basice concept but you should be able to implement it rather easily...you could make the search quicker(if your grid is small) if you pre store every possible path in a database and do a quick lookup as to ho to go from on to the next...
hope this helps, im sure there will be other ideas to follow from others...ciao
For that sort of thing you would use a flood-fill sort of algorithm. Pathfinding algorithms usually work so well because they limit the number of paths. Finding all of the paths is largely antithetical to that.
From an older project of mine.
some of the stuff is a little odd, but hopefully you should be able to get the jist of it.
From an older project of mine.
vine *hexeswithin(hexinfo *starthex,unitinfo *iunit, long maxsteps){//// Return a vine of hexes containing all hexes less than or equal to maxsteps away from // starthex for iunit.//vine *rtn=0;hexinfo *iunitprev=0;hexinfo *neighbor=0;int tt;vine *v;path *p;if (!starthex){ return(0);}if (!iunit){ return(0);}if (maxsteps<=0){ return(0);}iunitprev=iunit->hex;iunit->hex=starthex;(new vine(HEX,starthex))->top(&rtn);for (v=starthex->paths;v;v=v->next){ p=(path *)v->data; tt=p->ptype->traveltime(iunit,p); if (tt!=-1){ // recurse. if (starthex==p->from){ neighbor=p->to; }else{ neighbor=p->from; } (hexeswithin(neighbor,iunit,maxsteps-tt))->splice(&rtn); } // otherwise do nothing, the path cannot be travelled.}iunit->hex=iunitprev;rtn->unique(&rtn);return(rtn);}some of the stuff is a little odd, but hopefully you should be able to get the jist of it.
Just to let you know, I thought about those two ways, and I might have come up with a solution to this. Tang Of The Mountain's idea would have already worked if it wasnt for the different terrain types, but I combined this approach (sort of) with the flood-filling idea, although I am not too sure if I completely understood the source code.
I don't use the hexagon coordinates that are usually referred to in this forum, maybe you like my approach. Need to get some rudimentary artwork done so I can explain it better.
Stay tuned!
I don't use the hexagon coordinates that are usually referred to in this forum, maybe you like my approach. Need to get some rudimentary artwork done so I can explain it better.
Stay tuned!
Author
So I thought about my idea (thanks again for the suggestions), and I presented my idea to two friends of mine, and we couldn't find any errors in it. But before I start to explain What & Why, I thought I should show you the Hexagon coordinate system I came up with which is slightly different from the other approaches.
In my opinion, this system has two great advantages:
1. Unlike the coordinate system introduced on Amit's pages, this one starts at the upper left corner, just like we are used to do with 2D screens.
2. Now comes the tricky part - moving to another hexagon always changes your coordinates by two, no matter if North, South, NW, NE, SE or SW. Imagine you are starting on X2/Y4. If you move to X2/Y2, the Y coordinate has changed by 2. It doesn't matter if it is + or -, it's just important that your coordinates change by 2.
If you travel from X2/Y4 to X1/Y3, you also "spend" two movement points. One from X2 to X1, and the other from Y4 to Y3. As I told you, it doesn't matter WHERE the difference is, as long as you have spent two movement points. A unit which can move 6 hexagons would therefore be able to spend 12 movement points.
I hope I made myself clear with the example above. I will try to find the time and translate the complete 3 pages of hand-written (!) text tomorrow. If there any questions so far, I will hopefully be able to explain some more details.
In my opinion, this system has two great advantages:
1. Unlike the coordinate system introduced on Amit's pages, this one starts at the upper left corner, just like we are used to do with 2D screens.
2. Now comes the tricky part - moving to another hexagon always changes your coordinates by two, no matter if North, South, NW, NE, SE or SW. Imagine you are starting on X2/Y4. If you move to X2/Y2, the Y coordinate has changed by 2. It doesn't matter if it is + or -, it's just important that your coordinates change by 2.
If you travel from X2/Y4 to X1/Y3, you also "spend" two movement points. One from X2 to X1, and the other from Y4 to Y3. As I told you, it doesn't matter WHERE the difference is, as long as you have spent two movement points. A unit which can move 6 hexagons would therefore be able to spend 12 movement points.
I hope I made myself clear with the example above. I will try to find the time and translate the complete 3 pages of hand-written (!) text tomorrow. If there any questions so far, I will hopefully be able to explain some more details.
Nice one C-Row. I was working on this problem as well as I couldn't figure out to elegantly move around impassable tiles. You observation above as made it much easier for me to implement this in my game now. Big thanks.
My Project
My Project
Author
Glad to be of some help. Had a look at your game's website, and it looks great so far. I will hurry up with the translation, maybe I can help you some more. :)
Author
As I wrote before, moving from one hexagon to the other costs 2 MP (movement points), so a unit that can move 6 fields in one turn can spend 12 MP in total.
First of all, I created two tables (or arrays, but coming from the SQL side of things, using tables is easier) which look like this:
tbl_fields_closed
- field X (the field that was reached)
- field Y (...)
- from X (the field the unit came from)
- from Y (...)
- costs (how much it spent to get there)
This table stores all hexagons that the unit was able to reach during the finding process. The unit's starting point will automatically be stored in this table, since the unit can always "reach" its starting point of course. So we add:
-> X3, Y5 (the starting coordinates, of course you will only add 3 and 5), X3 Y5 again, and 0 as costs, since we didn't spend any MP to stay where we are
Now for each MP the unit can spend, we do the following:
1. At first, we look up all fields that are "closed". In the first run, we only have to check X3/Y5.
2. Now, we look for all adjacent tiles that we can reach theoretically.
- X3/Y3 is not closed -> possible
- X4/Y4 is not closed -> possible
- X4/Y6 is not closed, but unreachable (water or some other terrain the unit can't move on) -> not possible
- X3/Y7 is not closed -> possible
- X2/Y6 is not closed -> possible
- X2/Y4 is not closed -> possible
3. Then we test if those tiles can be reached spending the current amount of MPs. Since this is the first run, we can only spend 1 MP. Moving from one tile to another requires at least 2 MP, so in the first run, we can't reach any of the above tiles.
4. If there would already be another field in tbl_fields_closed, we would return to 2., but since X3/Y5 was the only field entered, the first run is finished now.
Second run - we can spend 2 MP now!
1. X3/Y5 is still the only "closed" field.
2. The second step is therefore still the same
3. This one varies slightly now. X3/Y3 can be reached by spending 2 MP, so it will be entered in "tbl_fields_closed". X4/Y4 and X2/Y4 also go there. For example, X3/Y3 will be entered like this:
tbl_fields_closed
- field X -> 3
- field Y -> 3
- from X -> 3 (the field we came from)
- from Y -> 5 (...)
- costs -> 2 (since we spent 2 MP to get there)
X2/Y6 and X3/Y7 still can't be reached, though, since they are more "expensive" than the normal fields. There could be a forest or some other problem with the terrain, so movement speed is not as good as on the other fields.
4. At the beginning of the 2nd run, X3/Y5 was the only closed field, so this run is now finished as well.
Third run - more to do!
1. There are four "closed" fields by now - X3/Y3, X4/Y4, X3/Y5 and X2/Y4
2. We will test X3/Y3 first this time, so I can show you the second interesting point about the closed fields
- X3/Y1 is not closed -> possible
- X4/Y2 is not closed -> possible
- X4/Y4 is closed -> don't need to check
- X3/Y5 is closed -> don't need to check
- X2/Y4 is closed -> don't need to check
- X2/Y2 is not closed -> possible
The point for not checking already closed fields is that they were already reached, either in this run or earlier, so there is no cheaper way to reach them.
3. Neither of them can be reached, though. To get to X3/Y1 this turn we would have to spend 2 MP, but in tbl_fields_closed we stored that we already spent 2 MP to get to X3/Y3, so there is only 1 MP left - not enough to get to X3/Y1.
4. Since there are more fields in tbl_fields_closed, we now do the same for the other fields - back to step 2.
This time, when we check X3/Y5, we can reach X2/Y6 and X3/Y7 as well. They cost 3 MP, and since we can spend 3 MP this turn, they will be added to the "closed" fields.
Fourth run - just to explain how we go on
1. As always...
2. When checking X3/Y3 again, we find the same fields as above.
3. This time, we can reach X3/Y1, since we can spend 4 MP now. We already spent 2 MP to get to X3/Y3 (saved in "costs"), so we can spend 2 MP more to get to X3/Y1 now. Enter it in the table to check it in the next run.
4. Same as before - more closed fields, more to check.
From X3/Y7 there is no way to reach X3/Y9 this turn, since we would have to spend 5 MP (2 to get there, plus 3 we already spent to get to X3/Y7). Same goes for the other adjacent tiles (X2/Y8 and X4/Y8). The other three tiles are either closed already or not reachable at all.
We do this until we reached the 12th run (remember, movement 6 -> 12 MP). All fields that are closed by then are in reach for our unit and should be visually be marked as so.
The main advantage of this is that this method also finds very strange paths that are nonetheless possible, as well as reacting to dynamically changing maps (sea can freeze over, roads can be destroyed etc.)
So basically, it is
1. Find all closed fields
2. Pick one, find all adjacent fields that are not closed (-> already reached) or impossible
3. Check wether or not these are reachable this run
4. Return to 2. to check the next closed field from 1.
5. At the end, show the player all fields the chosen unit can move to.
Of course you could start with 2 MP already, since no field is reachable with 1 MP only. Feel free to ask for further explanations if you need them. It's quite hard to describe unless you got it in your own head. Sorry.
First of all, I created two tables (or arrays, but coming from the SQL side of things, using tables is easier) which look like this:
tbl_fields_closed
- field X (the field that was reached)
- field Y (...)
- from X (the field the unit came from)
- from Y (...)
- costs (how much it spent to get there)
This table stores all hexagons that the unit was able to reach during the finding process. The unit's starting point will automatically be stored in this table, since the unit can always "reach" its starting point of course. So we add:
-> X3, Y5 (the starting coordinates, of course you will only add 3 and 5), X3 Y5 again, and 0 as costs, since we didn't spend any MP to stay where we are
Now for each MP the unit can spend, we do the following:
1. At first, we look up all fields that are "closed". In the first run, we only have to check X3/Y5.
2. Now, we look for all adjacent tiles that we can reach theoretically.
- X3/Y3 is not closed -> possible
- X4/Y4 is not closed -> possible
- X4/Y6 is not closed, but unreachable (water or some other terrain the unit can't move on) -> not possible
- X3/Y7 is not closed -> possible
- X2/Y6 is not closed -> possible
- X2/Y4 is not closed -> possible
3. Then we test if those tiles can be reached spending the current amount of MPs. Since this is the first run, we can only spend 1 MP. Moving from one tile to another requires at least 2 MP, so in the first run, we can't reach any of the above tiles.
4. If there would already be another field in tbl_fields_closed, we would return to 2., but since X3/Y5 was the only field entered, the first run is finished now.
Second run - we can spend 2 MP now!
1. X3/Y5 is still the only "closed" field.
2. The second step is therefore still the same
3. This one varies slightly now. X3/Y3 can be reached by spending 2 MP, so it will be entered in "tbl_fields_closed". X4/Y4 and X2/Y4 also go there. For example, X3/Y3 will be entered like this:
tbl_fields_closed
- field X -> 3
- field Y -> 3
- from X -> 3 (the field we came from)
- from Y -> 5 (...)
- costs -> 2 (since we spent 2 MP to get there)
X2/Y6 and X3/Y7 still can't be reached, though, since they are more "expensive" than the normal fields. There could be a forest or some other problem with the terrain, so movement speed is not as good as on the other fields.
4. At the beginning of the 2nd run, X3/Y5 was the only closed field, so this run is now finished as well.
Third run - more to do!
1. There are four "closed" fields by now - X3/Y3, X4/Y4, X3/Y5 and X2/Y4
2. We will test X3/Y3 first this time, so I can show you the second interesting point about the closed fields
- X3/Y1 is not closed -> possible
- X4/Y2 is not closed -> possible
- X4/Y4 is closed -> don't need to check
- X3/Y5 is closed -> don't need to check
- X2/Y4 is closed -> don't need to check
- X2/Y2 is not closed -> possible
The point for not checking already closed fields is that they were already reached, either in this run or earlier, so there is no cheaper way to reach them.
3. Neither of them can be reached, though. To get to X3/Y1 this turn we would have to spend 2 MP, but in tbl_fields_closed we stored that we already spent 2 MP to get to X3/Y3, so there is only 1 MP left - not enough to get to X3/Y1.
4. Since there are more fields in tbl_fields_closed, we now do the same for the other fields - back to step 2.
This time, when we check X3/Y5, we can reach X2/Y6 and X3/Y7 as well. They cost 3 MP, and since we can spend 3 MP this turn, they will be added to the "closed" fields.
Fourth run - just to explain how we go on
1. As always...
2. When checking X3/Y3 again, we find the same fields as above.
3. This time, we can reach X3/Y1, since we can spend 4 MP now. We already spent 2 MP to get to X3/Y3 (saved in "costs"), so we can spend 2 MP more to get to X3/Y1 now. Enter it in the table to check it in the next run.
4. Same as before - more closed fields, more to check.
From X3/Y7 there is no way to reach X3/Y9 this turn, since we would have to spend 5 MP (2 to get there, plus 3 we already spent to get to X3/Y7). Same goes for the other adjacent tiles (X2/Y8 and X4/Y8). The other three tiles are either closed already or not reachable at all.
We do this until we reached the 12th run (remember, movement 6 -> 12 MP). All fields that are closed by then are in reach for our unit and should be visually be marked as so.
The main advantage of this is that this method also finds very strange paths that are nonetheless possible, as well as reacting to dynamically changing maps (sea can freeze over, roads can be destroyed etc.)
So basically, it is
1. Find all closed fields
2. Pick one, find all adjacent fields that are not closed (-> already reached) or impossible
3. Check wether or not these are reachable this run
4. Return to 2. to check the next closed field from 1.
5. At the end, show the player all fields the chosen unit can move to.
Of course you could start with 2 MP already, since no field is reachable with 1 MP only. Feel free to ask for further explanations if you need them. It's quite hard to describe unless you got it in your own head. Sorry.
Quote:Original post by Anonymous Poster
although I am not too sure if I completely understood the source code.
In plain English then, perhaps it will be clearer.
The function takes a tile, a unit, and the number of steps left to go.
It returns a list of tiles [the tiles within the area you're looking for].
-First, add the start tile to the list. Since the unit is here it can obviously get to here.
-Then, for each neighboring tile, find the steps [movement points] it would take the unit to get to that neighboring tile from the start.
-If the unit cannot travel there, or the steps [movement points] are more than the unit has left [which is passed to the function], disregard that neighbor.
-If the unit can travel there, check if the neighbor is already in the list. If it is, disregard it.
-If it is not... Then call this function again, using the neighbor as the starting point, and removing the steps to get to the neighbor from the steps left. Take the list it returns, and add it to the list of tiles.
-Return the list of tiles.
... and that's it. The only tricky part is the recursion, and maybe some of the tile/neighbor abstraction. And it looks to be similar to what you've already described.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement