Chris hit it on the head, the question is: why? The answer to your question entirely depends on your answer to that question.
NathanRungeMember Since 08 Feb 2008
Offline Last Active Today, 09:06 AM
- Group Members
- Active Posts 288
- Profile Views 1,914
- Submitted Links 0
- Member Title Member
- Age 25 years old
- Birthday March 4, 1989
- Website URL http://www.ozymandias.com.au
Posted by NathanRunge on 06 April 2014 - 08:24 AM
Using a game class has a number of other potential advantages. Firstly, it can allow you to benefit from inheritance and polymorphism. If you're utilising an underlying framework, that framework might provide a Game class which can be extended, thereby handling much of the lower-level stuff. Certainly this can be handled using a number of separate systems, but there's certainly scope for conveniently handling timing values and calls to update the input system through a base class.
In the same way, you can benefit from polymorphism. In the Heron Framework, which I've developed and used for a number of years, there are multiple extensions to the game class that provide more specific functionality and, more importantly, there are different versions for different platforms. Once again, there are other ways to approach these issues but this is one convenient one.
There's also the possibility to consider scope for multiple 'games.' In Heron, there's a 'GameMode' class which provides the functionality of a game loop but is managed by a game. This effectively allows multiple 'Game'-type classes to be created, loaded, unloaded and run. In this manner separate components can be loaded separately and unloaded when not required, though this is usually handled in other ways. More often, I use this class to create a single game class in a portable library.
A final way in which multiple 'Games' might be employed are in tools. While not games, a number of the tools I have created employ Game classes to manage components that utilise the graphic device and may also employ the input system or content pipeline. In such cases it is beneficial to separate the game from the remainder of the application, and also sometimes necessary to create multiple games and run them simultaneously.
These are some of the reasons I, personally, choose to use game classes. Like rip-off, I also have an aversion to globals. That said, there are many other valid approaches to the problem, such as utilising a graph of systems and components.
Posted by NathanRunge on 16 May 2013 - 08:38 PM
I think, for the moment at least, we're looking to simplify the problem. As such, we're:
- Eliminating the possibility of moving platforms.
- Eliminating the possibility of mobile obstructions.
We're going to keep the data structures used to predict the positions of these elements in case we implement them in the future, but we think removing them for now simplifies the process of getting a working AI implemented, at least for a prototype. We do, however, have to keep mobile hazards. These are required for certain trap types, as I'll try to demonstrate in attached diagrams. These are basically rectangles that follow a time-keyed path, with an enumeration determining what they do at the completion of their path. Using a time-offset you can determine where they'll be in 't' seconds.
I completely agree with your take on the jump arcs. The plan, as it stands, is to calculate all jump connections at full horizontal velocity and a fixed jump velocity. For the purposes of a prototype I'll have all AI's featuring the same 'jump impulse'. In the future I may use a limited set of 'jump impulses' and use a dictionary to lookup the navigation data appropriate for that type of AI.
I definitely intended to calculate jump links after the platform information. Calculating during the build phase would certainly reduce the peak strain on the system and it's something I'll look into doing.
The current system calculates its path only if it's on a platform, otherwise it uses simple steering. I'm glad to hear you'd recommend that approach. Regarding the creation of nodes, are you recommending creating a series of jump links along the platform, each one having a position on the platform in addition to a destination on the target platform and a velocity? Would the AI run between these link locations and jump if it meets the requirements? Or would we simulate AI actions, such as I described in my previous post? If so, would jump only be considered an option at a jump link point? Or would it be best to pre-select a jump link to use and the propagate actions to reach that link?
Even though we're removing mobile obstacles for the time being, I'll briefly address them. Mobile obstacles are similar to mobile platforms in that they move and may obstruct the player, the difference being only that mobile platforms are flagged to be considered by the pathfinding system. In the case of player-placed obstacles they would follow the same restrictions as all other traps and obstacles, and would not move in such a way as to obstruct the edge of a platform. Rather than using plathfinding to validate player-placed items, we use a simple set of rules to prevent impassable areas. Obstacles and traps must be spaced at particular intervals, can't sit right at the edge and mobile obstacles don't roam, but follow a pattern.
I'll also address mobile hazards. The most obvious example would be minions, which may patrol an area. Others include 'swinging traps', for example. Say a swinging hammer which moves back and forth. While the base remains fixed, the area considered to be dangerous moves and the AI would need to consider how best to avoid that danger.
Recapping the Plan
I'm trying to take all these discussions and your very helpful advice and hammer it into a plan going forward. The only area that concerns me overly much at this stage is the 'action planning' phase during run-time. In my previous post I described creating a graph of possible actions, but this didn't properly account for a series of jump links. Is creating that sort of action graph how you would recommend approaching it, or should the AI really be using standard pathfinding, following the available platform space until I reach a jump node that it can use or it runs out of space. In doing so I would need to simply scan for obstacles immediately ahead and react on the fly which won't produce the best results but would be a lot more resource efficient than simulating many actions to find the next platform.
If I continue by simulating actions and navigating the action graph using A*, how do I approach the jump links? Should the AI try to navigate to one of them, or assess them on the fly? Do these links dictate whether the AI should simulate jumping actions, or do they just inform the AI that it can try jumping to another platform from here if it meets its requirements? Would that not also be accounted for by simulating the available actions?
Thank you once again for all your help.
Posted by NathanRunge on 15 May 2013 - 09:06 PM
Hi again DrEvil,
I'll try to clarify what I meant on those couple of points. Regarding excluding the requirement for a 'run-up' I should have been more specific. I believe I can exclude the requirement for back-tracking for the purposes of a run-up and simply force the AI to work with what space it has available. I feel this can be justified because slowing the 'hero' is a legitimate tactic to bring about its demise and the death of the AI is a positive event for the player, rather than a negative one. I can't really cheat and force the velocity to maximum as I believe this would prove frustrating to the player, but rather simply allow the AI character to die if it cannot achieve the required velocity.
Regarding the modifier for jump heights, I meant that to mean that different 'heroes' have different jump 'impulses', that being different (negative) Y velocities, therefore also meaning a longer jump time. Normally I work with proper vectors, a direction and a magnitude, but have found it beneficial to deal with the X and Y components separately in this case. Your experience would suggest reversing that? From either basis I can calculate the required impulse, given a horizontal momentum, or a required momentum given a fixed impulse. Typically I have calculated connections based off a fixed impulse and then determined the required momentum.
Regarding the jump trajectories, that seems like the most sensible way to approach the problem. You would recommend doing so when preparing all the platform navigation data following the 'build phase'? We're using a proprietary framework and we're currently using simple AABB collisions, but will be hopefully be switching over to a swept AABB solution shortly, having partially implemented it already.
Regarding the collisions, you're speaking about a simple occupancy grid with collision detection then taken if the area is 'occupied'? The tile grid structure we're using maintains its own occupancy grid which may prove useful in this case. I think simulation, as you described, will be a necessary route and I recently restructured the character class to separate out the simulation elements required. This way we can simulate all the actions using a tight loop, without needing to separate out the physics system.
So, if I try breaking down my imagined process at this point once more it looks like the following:
- Put together the platform information from the terrain and obstacle data.
- Process connections between each platform by:
- Determining which platforms are theoretically within range of a hero's jump.
- Simulating each jump at full speed against static obstacles.
- If the jump lands on the target platform, add the connection to the navigation data.
- If the current plan isn't valid...
- Get the connections for the current platform.
- Iterate along connections until a series of routes of suitable length are created.
- Sort routes using a heuristic. Basically Progress - Danger.
- Create an action plan for the first few routes (if we can afford it) by:
- Creating a graph of possible actions by...
- Creating a node for each initial action.
- As nodes are created, assign them a score and cost. Score being progress to the next platform in the path. Cost being damage taken.
- Choose the best node (Score - Cost) and create all possible actions from that node at, let's say, 0.25 second intervals. Close the chosen node.
- Iterate through the nodes, choosing the most promising each time until the goal platform is achieved.
- Hopefully, by using a heuristic during the creation process, we can avoid chewing up 20Gb of memory not to mention the processing time.
- Creating a graph of possible actions by...
- Choose the best of these plans, Total Score - Total Cost.
- Follow the action plan until it's invalidated.
Is this somewhat how you would approach the problem? Ideally I'd like to shift the simulation into the preparation phase, but mobile obstacles complicate that idea. It's the 'planning' phase that concerns me the most. It could be simplified by selecting a connection point along the existing platform and navigating to that point, then jumping, but once you throw in hazards and obstacles the decision making process becomes much more challenging. Is creating a graph the best approach, or would it be best to create a much simpler plan and use in-the-moment sort of decision to try to reach those simpler goals?
Thanks once again,
Posted by NathanRunge on 14 May 2013 - 07:50 PM
Firstly I want to thank you for taking the time to help out, it's definitely appreciated. I'll try to fill in all the details that might help.
Regarding acceleration, it's reasonably quick. More importantly, I've come to the realisation that the player's goal is to kill the AI and, as a result, I can simply handle acceleration in a very 'stupid' way and accelerate until speed is sufficient to make a jump or the character runs out of platform. I can exclude the requirements for planning run-ups in any complex way.
Game World Size: We think the average world size may be about 12 tiles (1200 logical pixels) by 70 tiles (7000 logical pixels). Give or take quite a bit. Currently the AI is designed to only plan about a screen size ahead, however.
AI Count: In most cases we'll be considering single-digit numbers.
Varying Paths: Different paths are not, strictly speaking, a requirement, but the AI should be choosing paths that present the least danger, and that may vary as hazards are added/moved/removed.
Attacking Defences: The AI are, as the design stands, strictly avoiding the defences. If we wish to change that in the future we'll obviously need to consider the feasibility of its implementation. The exception would be 'minions' which we can hopefully have the AI consider harming if it presents the best option to progress safely.
Tile Alignment: The environment is tile-based but obstacles and hazards are not constricted to the grid.
Overlapping Platforms: The game world, with which the characters interact, is entirely two dimensional. I'm not entirely sure what you mean by overlapping platforms. If you mean platforms being vertically over another, then yes this is possible. If you mean something like in the first image I've attached, then no. Tiles may be made passable, but if so they're not considered to be platforms and the character will fall through them. We have support for one-sided platforms in obstacles not aligned to the grid, but this isn't a core feature. If you meant something else, please just let me know and I'll clarify.
Slopes: Our level system supports slopes but we may not use them as they present a complication that isn't necessary. If we do implement them we may simply maintain horizontal speed to simplify the AI process.
1-Tile Gap: The simple answer is 'no'. The collision box is thin enough so that characters will fall into 1-tile wide holes. If the framerate dropped dramatically, it's possible the character could overshoot such a hole by moving too much in one frame. That's something we should eventually get around to fixing though.
Static Platforms: As it stands, all tile-based platforms are statically placed. We have support for moving platforms, which I think would be a nice touch, but are less important than implementing an effective AI pathfinding solution. The AI has access to movement information about these mobile platforms in the same way it has access to this information about hazards and obstacles. That said, I like your suggestion of attaching single on and off platforms for moving platforms, much simpler to calculate.
Obstacle Placement: Obstacles cannot be placed within a tile (100 logical pixels) of a platform end. We can extend that to two tiles. This is to prevent the player from creating impossible to traverse environments.
Regarding the performance concerns, these are definitely real. I've started to address the problem by breaking down the planning procedure across multiple frames to reduce the peak load. Other important steps will be to only recalculate paths when necessary and 'heroes' should be spaced out so that only, at most, a couple should be calculating routes at the same time.
If we end up implementing any special circumstances where there will be a larger number of 'heroes' we'll definitely implement a collective path-finding solution that will only need to be recalculated by individual agents if that path is dramatically disrupted (such as if they take damage and are knocked out of place).
Regarding the weighting map, while one path isn't a huge problem, the issue I would see is adapting to mobile hazards. Regarding sliding, that's primarily intended to provide additional options for the AI to avoid hazards, rather than navigating the environment. We thought creating spaces that must be slid through would unnecessarily add to the complexity of the pathfinding without adding anything important to the game.
Finally, I think pre-calculating the jump links and related data may definitely be the way to go. Currently we have a modifier that changes the jump height of various AI's. Is there a way you would suggest handling that? It's something that can be cut if it adds too much complexity.
Posted by NathanRunge on 10 May 2013 - 02:00 AM
While simplifying the underlying system would certainly make approaching the AI problem a lot easier, it's unfortunately not possible for the game in question. Acceleration and multiple, dynamic obstacles are all rather essential components, though at least collisions are all through AABBs. Without these features I could certainly have already implemented a solution.
Considering that the player's goal is to eliminate the hero, and modifying the hero's speed is one way to achieve this goal, I may be able to exclude back-tracking and simply have insufficient momentum lead to hero death. Obviously this wouldn't really work in cases where the character's survival is a desirable outcome, but it may suit this game. Just some thoughts that have circulated today.
Posted by NathanRunge on 09 May 2013 - 04:03 AM
Good day everyone,
I have been developing a game which can be described as a 'side-scrolling tower defence' or 'reverse platformer', in which players take on the role of the traditional 'bad guy' and deploy traps, obstacles an minions to a side-on level in an attempt to prevent the 'hero' from reaching the end. Obviously the AI for the 'hero' is going to prove extremely important.
I think I've formed a reasonable high-level view of how to approach the problem, though I'm certainly no expert and welcome being told otherwise. It's the implementation of these concepts I'm struggling with the most, however, and I was hoping I may be able to find some assistance here.
The goal of the AI remains the same at all times, to reach the end of the level. In doing so it must navigate the geometry of the level and, to the best of its ability, avoid taking damage or being killed by the array of obstacles placed by the player. In consideration of the problem, I decided that the AI needed to create a plan. This is because it needs to consider whether jumping to a platform presents an ongoing path, or whether jumping now will place the character in more danger than jumping later. Once again, I'm new to AI programming so I fully acknowledge I may be over-thinking or poorly designing my approach here.
How I'm currently approaching the problem can be considered in a number of layers:
- A heuristic. Currently this is simply 'positive movement on the x axis multiplied by 2'. In the future, levels may include a simple A* graph, the heuristic of which being reducing distance toward the 'goal node'. This allows for more complex, multi-route levels.
- What could be termed a 'navigation mesh'. At the completion of the game's 'build phase' the level geometry is scanned and a series of 'walkable lines', or 'platforms', are created to inform the AI of walkable areas.
- The AI, when recalculating its plan, determines which platforms it can reach from its current platform, then extrapolates similarly from each of these, excluding back-tracking and known dead-ends, until it has a plan at least 700 logical units in either direction. It should only back-track if it has no route forward, and when a platform has no route forward it is listed as a dead-end to back-and-forth over the same area.
- As these paths are generated they're assigned a cost based upon movement required and extra cost for jumping or sliding. The cost is meant to simulate both the 'effort' and 'difficulty' of the plan. They're also assigned a score based on the aforementioned heuristic. When all the paths have been found they're sorted by score - cost. I can happily fiddle with the sorting later.
- This is where it begins to, perhaps, exceed my knowledge and experience. The next step is to generate a plan, or series of plans, for the first few paths, or onward until a path is found that doesn't result in death. I'm having a great deal of difficulty determining how to generate this plan. Does one simply simulate every possible action at timed intervals and choose the best result, or does one attempt to direct simulation toward the goal using various formulae to calculate stopping distances, run-up requirements, etc? Do you then randomly vary that plan to find the optimal solution? How do you choose when to jump, or what if the hero requires a run-up to make a jump? If this approach makes sense, do you have any recommendation on how to implement it?
- These plans are then sorted based upon the (score-cost) of their underlying paths, with additional penalties imposed by taking damage or needing to avoid additional hazards.
Any advice you could give regarding the approach would be truly appreciate, and I must admit this process has proven rather disheartening thus-far. There is obviously a great deal of room for improving efficiency in this model, but flexibility and a 'human-like' process are important. I know that I could bake jump nodes into the navigation data, but I feel this would compromise these important characteristics and prove a sub-optimal solution.
Thanks for any help you can give, once more.
Attached: 2 screenshots from a prototype showing the platform detection.
The hero character has a small selection of options available: Move Left, Move Right, Jump, Duck, Do Nothing. Ducking while moving initiates a slide. 'Do Nothing' will slow the hero to a standstill if the character has momentum. Moving left and right is at a much slower rate if airborne.
I'm considering using a GOAP-like planning system to determine actions, as this would provide the AI with ways to chain together the actions needed to achieve the task. A number of problems arise, however. The first being that planning systems need to work backward from the goal. That makes checking for mobile hazards and obstacles a bit more challenging. The second question is how far you would break down actions? Would you break them down to the 'jump', 'run', 'duck' level, or something more complex such as 'run up', 'jump to platform', 'avoid obstacle', 'slide under trap'. My inclination would certainly be the latter.