One thing which has been a cornerstone of my development framework so far has been Large Monster Implementation (from this point referred to as LMI). It's something that I've said I wouldn't give up on.
So as it became increasingly likely that LMI wasn't going to work, or was going to have to require two completely different movement and combat systems working in tandem I became a little downhearted.
I had built my level prefabs to include a two square wide door, specifically to allow plus size monsters. Many of the monsters I had already designed had small and large variants. It was a real downer.
Anyway, my original plan was to have two sets of tile data, one for small tiles and one for large. I would keep track of movement in both, and then share data between them. it was horrible complex to try and code, and I just gave up, just trying to work around the issue on other things that I could actually do.
Today I though again about my reasons for using two sets of tile data. Why separate things? A large monster takes up 4 tiles, so we could get the second set of data by checking every group of 4 tiles in the first data set and then checking to see if any of them are occupied. We could do this when building the map, and then update the data sets every time someone moves. But what if we check the tiles only when we need to?
Lets look at an example:
Right now every walkable tile in the game is stored in a dictionary. We can set whether the tile is walkable, whether it blocks vision and who or what is occupying the tile. We can select a tile by clicking on it and checking who is occupying it. When characters move from tile to tile they clear their presence on the old tile and set it on a new one. Because character moves in this game are upwards of 6 tiles per turn (instead of the traditional 1 tile movement of most rogue likes), I only need to change the occupier reference in the start and end tiles of the movement. The path-finding script takes care of what happens between those tiles.
The pathfinder in fact consists of two parts, the graph builder which gets walkable tiles from the map, and the path-finding algorithm (which is again split in to two parts, a simple Bresenham's line script and an A star algorithm for if more complex movement is required).
Before getting passed to the pathfinder the graph can be built to take in to account the possibility of large monsters. By checking if each square is walkable, and if it's 3 neighbors are also walkable we can check for a 2 square wide path instead of a single width path.
So we check the actual location of the spider and its neighbors using a search array:
add_to_graph = True
We keep going, filling up the graph to the extent of the monster's maximum movement range or the distance of the goal. Then we hand off to A* to try to make a route to the goal.
In this case the route is blocked, the actual A* would try a lot more routes than this one, I do have a variant which will find the best square from the closed list and path find to there too to get as close the goal as possible rather than just giving up.
If we remove the blocking square the spider will go all the way to the goal.
We have to do more things to get this to work, for example when moving the spider we have to give it an offset so visually it appears in the center of the 4 squares. We also have to set all the 4 squares as occupied and set the occupier as the spider. When moving to a new position we also have to clear all the occupied squares.
If e do it right clicking on any of the 4 squares will return the spider as the occupier. This will allow the player to select the monster for a combat target, or to shoot at it, or cast a spell on it or loot its corpse or interact with it in any other way without ever knowing that it really only occupies one square.
But... I do have more headaches in store, one of which is the fact that the Bresenham's line script actually runs before the graph builder (to try and save processing time, building a graph can be time consuming) so the Bresenham's line script will also have to be modified when dealing with large monsters. Or we can just skip linechecks for large monsters, baring in mind they are going to be quite few and far between.
Setting aside such problems for now, it seems like the LMI problem may have been partly solved, and the implementation can also be shared by such things as large pieces of furniture
So as it became increasingly likely that LMI wasn't going to work, or was going to have to require two completely different movement and combat systems working in tandem I became a little downhearted.
A giant spider, and look, it really is GIANT!
I had built my level prefabs to include a two square wide door, specifically to allow plus size monsters. Many of the monsters I had already designed had small and large variants. It was a real downer.
Anyway, my original plan was to have two sets of tile data, one for small tiles and one for large. I would keep track of movement in both, and then share data between them. it was horrible complex to try and code, and I just gave up, just trying to work around the issue on other things that I could actually do.
Today I though again about my reasons for using two sets of tile data. Why separate things? A large monster takes up 4 tiles, so we could get the second set of data by checking every group of 4 tiles in the first data set and then checking to see if any of them are occupied. We could do this when building the map, and then update the data sets every time someone moves. But what if we check the tiles only when we need to?
Lets look at an example:
A spider ready to move across our large room.
Right now every walkable tile in the game is stored in a dictionary. We can set whether the tile is walkable, whether it blocks vision and who or what is occupying the tile. We can select a tile by clicking on it and checking who is occupying it. When characters move from tile to tile they clear their presence on the old tile and set it on a new one. Because character moves in this game are upwards of 6 tiles per turn (instead of the traditional 1 tile movement of most rogue likes), I only need to change the occupier reference in the start and end tiles of the movement. The path-finding script takes care of what happens between those tiles.
The pathfinder in fact consists of two parts, the graph builder which gets walkable tiles from the map, and the path-finding algorithm (which is again split in to two parts, a simple Bresenham's line script and an A star algorithm for if more complex movement is required).
Before getting passed to the pathfinder the graph can be built to take in to account the possibility of large monsters. By checking if each square is walkable, and if it's 3 neighbors are also walkable we can check for a 2 square wide path instead of a single width path.
So we check the actual location of the spider and its neighbors using a search array:
add_to_graph = True
search_array = ((0,0)(1,0),(1,1),(0,1))
for xy in search_array:
check_x = own_x + xy[0]
check_y = own_y + xy[1]
tile_key = get_map_key(check_x,check_y)
if tile_key in walk_dictionary:
if walk_dictionary['tile_key']['occupier'] != None:
add_to_graph = False
else:
add_to_graph = False
If add_to_graph is True we can add the square to the graph, knowing that it has enough room around it for the spider to walk through.
We keep going, filling up the graph to the extent of the monster's maximum movement range or the distance of the goal. Then we hand off to A* to try to make a route to the goal.
In this case the route is blocked, the actual A* would try a lot more routes than this one, I do have a variant which will find the best square from the closed list and path find to there too to get as close the goal as possible rather than just giving up.
If we remove the blocking square the spider will go all the way to the goal.
We have to do more things to get this to work, for example when moving the spider we have to give it an offset so visually it appears in the center of the 4 squares. We also have to set all the 4 squares as occupied and set the occupier as the spider. When moving to a new position we also have to clear all the occupied squares.
If e do it right clicking on any of the 4 squares will return the spider as the occupier. This will allow the player to select the monster for a combat target, or to shoot at it, or cast a spell on it or loot its corpse or interact with it in any other way without ever knowing that it really only occupies one square.
But... I do have more headaches in store, one of which is the fact that the Bresenham's line script actually runs before the graph builder (to try and save processing time, building a graph can be time consuming) so the Bresenham's line script will also have to be modified when dealing with large monsters. Or we can just skip linechecks for large monsters, baring in mind they are going to be quite few and far between.
Setting aside such problems for now, it seems like the LMI problem may have been partly solved, and the implementation can also be shared by such things as large pieces of furniture
Comments
Post a Comment