Jump to content

  • Log In with Google      Sign In   
  • Create Account

2D Platformer AI


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 NathanRunge   Members   -  Reputation: 541

Like
2Likes
Like

Posted 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:

 

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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?
  6. 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.

 

Nathan Runge

 

Attached: 2 screenshots from a prototype showing the platform detection.

 

Addendum 1

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. 

 

Addendum 2

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.

Attached Thumbnails

  • Boss Platforms.png
  • Boss Platforms 2.png

Edited by NathanRunge, 09 May 2013 - 05:37 PM.

Personal Page: http://www.nathanrunge.com/     Company Page: http://www.ozymandias.com.au/


Sponsor:

#2 DrEvil   Members   -  Reputation: 1105

Like
2Likes
Like

Posted 09 May 2013 - 05:47 PM

Path planning with a physics element to it can get very tricky and very fast, and very expensive. If you've seen the super Mario AI and some of the articles and debug graphics on how it plans you can get an idea.

At the high level, the planner is looking for a way over and around obstacles. Those paths may involve very specific jump timing such that if you don't have the luxury of preprocessing the map to find jump segments you are potentially looking at doing some expensive runtime calculations. Depending on how complex the obstacles will ultimately be, you might only need to rebuild a dynamic graph whenever obstacles are added or removed. If the obstacles might be complex and involve the need to make jumps at variable speeds for example, then I would say you should first simplify your problem.

If you can settle on a small set of deterministic behavior it will ease the implementation of both a preprocessing step and a runtime planner should you need it.

For example, if you can narrow down the potential player speeds to 1 fixed speed, such that the number of expansions from a node is small you will have a far easier time. If the AI accelerates and the speed can be a wide range of values the complexity explodes, because the planner may have to explore backtracking in order to run up enough speed to make a jump. Rather than realistic physics, you could optionally make the interpolation from stopped to running and running to stop their own discrete planning states if you don't like the way an ai looks starting and stopping on a dime. I would add that as a 2nd step though once you have him working via simple means.

Ultimately the complexity of the possible obstacles in your game are going to make a big difference to the complexity you'll need.

#3 NathanRunge   Members   -  Reputation: 541

Like
1Likes
Like

Posted 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.


Personal Page: http://www.nathanrunge.com/     Company Page: http://www.ozymandias.com.au/


#4 DrEvil   Members   -  Reputation: 1105

Like
3Likes
Like

Posted 14 May 2013 - 06:41 AM

Fair enough. If the acceleration is fast enough it can probably be sort of hidden away in the planner. For example, if you can get by with jump planning from a run such that jumps links in the planner have basically a deterministic trajectory, generated from the max run speed and jump velocity, the planner could handle the situation by adding a small run expansion that represents acceleration to max speed such that the remaining expansions of the planner is sort of simplified at that speed threshold. This intial expansion is only necessary if the A.I. isn't already moving .

 

The point being, that if the physics involves a slow acceleration like a multi-second run up to meet max speed and the planner needs to compensate for a wide range of jump takeoff speeds, the planning will likely get very expensive, and not only that the reliability of the planner is going to be largely based on how well the planner can represent the physics of your character.

 

Other important details.

How large are the game worlds?

How many A.I. will be attacking at once? A tower defense sort of game implies there will be a number of them.

If there are many A.I attacking, does gameplay require that they vary their paths?

Are A.I. strictly going to try and navigate over the 'defenses'? Or are there situations where they should attack them?

Are the obstructions and platforms all tile-aligned?

Is the game world going to be sort of 2.5D like the 2 screenshots? Or will it have overlapping platforms?

Are there going to be slopes that affect speed?

Is the speed such that you can run across 1-tile gaps such as in screen shot 1? (ala super mario bros)

Are platforms statically placed? If so it would be a big boon if the platform jump links can be statically calculated.

Can obstacles be placed at the end of platforms such that their traversal can be cut off entirely?

 

From the screenshots, it looks like you might be dealing with a tile aligned geometry. I don't know if that holds up to the obstructions that can be added as part of gameplay, etc.

 

I would probably start my planner with expansions at tile intervals, or intervals the size of the character bounds. I would start essentially a flood fill at the A.I. spawn position, expanding at these interval steps to the end of the map. Initial thoughts of how to expand on each node

  • Expand horizontally left and right 1 tile or interval, whatever size that is. That node should have the expected speed of accelerating in that direction. If the first tile is from 0 velocity, the first expansion of the search will be 0 * acceleration * interval. The speed must be part of the criteria for looking up 'existing' nodes in the open and closed list of the A* to prevent. Speed basically makes it a 4 dimensional search, such that basically every locational node that can be generated can have multiple planner nodes for it, each representing a different speed, which may have involved back tracking and run-ups to reach, etc. A 3rd expansion may be necessary if one of the options is to maintain current speed(which may not be max speed). Be as conservative as you can here, because the added variability in speed based expansion explodes the search space exponentially.
  • I would probably try to ignore the vertical aspect of planning to start with, such as creating nodes floating in space that represent jumping or falling. This might perhaps need to be revisited later when it comes to running off platforms and potentially steering to destinations and stuff, but maybe not depending on the level complexity.
  • Since presumably jumps and other such traversals may involve variable speeds, you kinda need to expand in each direction twice, once representing accelerating in that direction, once representing decelerating in that direction. Generally platformer physics don't have the same deceleration ramp as they do acceleration, even better if they have rapid stop sort of animations, as that will reduce the number of expansions needed for deceleration path. Deceleration expansions are necessary for jumps that may require slower than maximum speed. If your game can work without that I would recommend avoiding this though, because this is where the cost is going to really explode. By work without that, I mean if all your jump links can be assumed to be jumps from max lateral velocity. I don't think the various super mario brothers bots bother with this added complexity in their planner, which is characterized by the A.I. just hauling ass through the maps. It may be though, and just picking the fastest path, but I haven't seen one navigate tricky jumps of some mario levels that require more finesse with your speed.
  • If the platforms are static, I would precalculate the jump links offline such that for any map you load, it has jump links that basically slot in to your search. For instance, if you were expanding at the interval of your tiles, you would have tiles connected to tiles of other platforms generated as a pre-process. During your run-time search, if you expand to a tile with a jump link, allow the expansion to take that link if it matches the speed threshold of the jump link. As a result, this link may only be navigated by paths that have had sufficient run-up, while paths too close would only have the option to run back or forward.
  • If you can't pre-process the platforms, and/or if they are completely blockable at runtime. I would still create a builder time spliced as part of your game loop, or perhaps offloaded to a thread, that can take a horizontal window of the game world and build platform jump links. When new obstacles are added invalidate the links that go to-from that tile and mark that area for rebuilding. When obstacles are removed, mark it for rebuilding. The point is to allow the planner to treat the links as if they are simply there, and not have to do physics or trajectory tests as part of its search loop. Whether they are statically offline built or build and runtime and cached, it should look the same to the planner.
  • I recommend avoiding moving platforms because they will likely involve continuous planning. If you can't, you can save a lot of planning if you can precalculate and mark platform line segments that represent what platform should be the boarding and exit platform, such that you would only need to do continuous jump tests between the boarding and movign platform or the moving platform and exit platform at any given time. A preprocessor could also be used to precalculate platforms that can potentially jump to a moving platform somewhere along its travel.

 

You can tell by the depth of the expansion even a single step that the cost even for 1 AI is going to be high, multiplied by multiple agents if you expect agents to pick different paths and/or adjust to threats along certain paths, etc, it will likely be a performance problem.

 

If you don't need guys to take different paths, or be penalized for defended paths and adjust their route, there are some things you can do to re-use the search state of a single search.

 

If you did a single search from the start of the map to the end, you should be able to generate essentially a weighting map by flooding a cost from the destination back through the entire search tree and all the closed nodes, such that each node knows the next best node to follow to get a step closer to the goal. This means that for any tile on the map, an AI simply has to follow that graph in decreasing cost until it reaches the goal. The speed is the obvious win here, a single search can be re-used indefinately, and can be updated whenever something in the map has changed. The downside is obviously that all the AI would be taking 1 path, so you can't really adapt for dynamic weighting for different AI, etc.



#5 DrEvil   Members   -  Reputation: 1105

Like
2Likes
Like

Posted 14 May 2013 - 07:14 AM

Also, re-reading your addendums, in the details I've described, it would be necessary to also expand slide links from any node with a speed threshold that can perform the slides. If the slides have the purpose to go under low overhangs, you'd probably want the planner to only branch slide nodes if the destination node is marked as low ceiling or whatever, to prevent unnecessary slide expansions arbitrarily out in the open or something.

Also, speaking of how you describe pre-processing the platform line segments at the end of the build phase, I would strongly suggest pre-processing the jump links during the same phase. It may also be useful to the planner to precalculate the floor to ceiling clearance of each platform segment if there may be overhangs. I would even likely split a long ground segment into multiple segments if it had a platform above part of it. Knowing the ceiling height from any given location can save the jump builder from attempting to do jump trajectories from tiles with too little clearance, and may have uses to simplify some of the planner.
 



#6 NathanRunge   Members   -  Reputation: 541

Like
1Likes
Like

Posted 14 May 2013 - 07:50 PM

Hi DrEvil,

 

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.

Attached Thumbnails

  • overlap.gif

Personal Page: http://www.nathanrunge.com/     Company Page: http://www.ozymandias.com.au/


#7 DrEvil   Members   -  Reputation: 1105

Like
2Likes
Like

Posted 15 May 2013 - 09:46 AM

Not sure what you mean about excluding run up requirements, unless you are saying that you could sort of cheat the jumps when they reach the jump link and set them to the appropriate jump velocity regardless of their velocity when they reached the jump link. If that is the case that certainly simplifies things hugely.

For obstacle placement, you seem to have thought about what I was referring to already, and that is building stuff on the edge of platforms to block routes entirely. Presumably 100 pixels is enough room for the AI to jump up onto and then jump over the obstacle.

I'm not sure what you are asking about the modifier to the jump heights. In my experience doing evaluations with trajectories I would generally work with jump velocity and angles. Mostly in getting my bots to calculate what angle to toss a grenade given a known grenade velocity in order to hit a target at some position. Launch angle trajectory calculations can provide 0-2 results. 0 of course if there is no solution, but up to 2 real solutions for a trajectory, with one of them being a 'mortar' style trajectory, which is probably the one you want to use in the context of jumping. I would use a start position, have an end position in mind, and need to calculate the launch angles for a known initial velocity.

I would do basically the same thing for jump trajectories. After you calculate each of your platform segments, loop through each platform segment and sample at some interval along the segment as a start point, and then loop through other segments and calculate a trajectory from those sampled start points to a destination point on the end of the other platforms on the non buildable buffer zone with your fixed jump velocity. The jump is only possible if the 'mortar' trajectory is valid, or the trajectory max height exceeds the destination point. The expensive part of trajectory calculation is validating the trajectory against the collision. The trajectory calculation is a relatively simple math evaluation, but you would still need to validate the arc of the trajectory with the world collision to make sure a jump trajectory isnt blocked by something. For grenade trajectories we would generally treat them as point entities and do raycasts at smallish intervals along the trajectory. For jump trajectories you would probably need to shape cast with the player bounds by sweep testing the player box along the trajectory. The jump should be considered valid if it ends up landing on top of the desired destination platform. Ultimately you end up with mathematically valid trajectories that need to be filtered by their legitimacy against the world collision.

Your collision routines are obviously a huge factor in how performance intensive this in. It sounds like the world is tile based, while the buildables aren't necessarily. I'm not sure what you are using for your collision/physics, but libraries like box2d and such generally support the ability to do swept collision of a shape.

Some performance considerations that might be viable for your situation.
* To avoid the worse cast of N^2 trajectory calculations between all segments, consider an interval tree or something to efficiently pick from the subset of possible destination platforms.
* Think about how to avoid doing the stepped collision tests of the trajectory altogether. Profiling is probably important here to see what actually works and what doesn't. Since all the tests are typically small time steps that involve a small amount of motion of the shape in order to imitate the jump arc, you might for example maintain a bit array of 70*12 such that you can map the start and end points of the stepped line to tiles in this bit array. If the bit is set, that means there is some collision somewhere in that tile, so you need to do the test, but if the bit is clear you can avoid doing the possibly more expensive test. Caching the overlapping tiles between frames could result in frequently rejecting the full collision tests because the cache will be valid for a number of frames until it moves enough to cross into a new set of tiles. Also, maybe to avoid the broad phase of doing individual stepped tests, maybe do a single broad phase that represents the entire axis aligned box from the start position to the destination position to cache the potential collisions and then do your stepped tests against that subset if your physics supports something like that.

Some useful resources
http://hyperphysics.phy-astr.gsu.edu/hbase/traj.html
http://digestingduck.blogspot.com/2011/07/paris-gameai-conference-2011-slides-and.html

If I were implementing a side scroller, I think I might initially try to leverage the physics system to tackle the jump calculations for me, especially if it were an offline preprocess. I'm not sure how well this would scale to runtime in your case. I would calculate the potential trajectories with the math equations, and then for each potential set of jump and land points I would add a temporary copy of the AI physics shape to the simulation at the start position, and seed them with the jump velocity, disable collision between them(since there will be hundreds or maybe thousands simulating at once), and then spin the physics tick in a tight loop using the same time step the game uses during normal play. This loop would abort when all these ghost actors finished moving or had the first contact with a walkable surface normal. In theory by doing it this way you get the most accurate calculation of jump links using essentially an identicle simulation environment as the runtime will use. It also opens up the ability for more complex jump links to be created. Suppose there is a jump that hits a platform that blocks motion, but that still safely falls down onto the desired platform. Without simulating the bouncing, sliding, velocity clipping yourself in a custom preprocessing, you wouldn't be able to detect these circumstances. If you let a physics simulation run as fast as it can to do the work for you, it can detect those situations with the same physical properties as the runtime, so you'd be free to add bouncing properties to certain AI and such that would be automatically accounted for in the jump calculations.

Taken further to illustrate the benefit, if I were making a side scrolling shooter that had grenade tossing, I would probably maintain a copy of the world physics simulation(without the moving objects) running non stop in a separate thread, such that AI could add a ghost grenade to this accelerated simulation using various throw velocites and it would simulate them in a deferred manner and when those ghost objects are finished moving, or when they outlive their grenade timer, I could evaluate the final result position to gauge its viability with respect to enemy positions. A given velocity might involve a bunch of bounces off various surfaces based on the physics characteristics of the grenade. The point is that since it uses the same code paths, same physical properties of the AI/grenade, same time step, it should be the best possible 'forward looking' way to consider different scenarios of velocities.
 



#8 NathanRunge   Members   -  Reputation: 541

Like
1Likes
Like

Posted 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:

 

Preparation Time:

  1. Put together the platform information from the terrain and obstacle data.
  2. Process connections between each platform by:
    1. Determining which platforms are theoretically within range of a hero's jump.
    2. Simulating each jump at full speed against static obstacles.
    3. If the jump lands on the target platform, add the connection to the navigation data.

Runtime:

  1. If the current plan isn't valid...
  2. Get the connections for the current platform.
  3. Iterate along connections until a series of routes of suitable length are created.
  4. Sort routes using a heuristic. Basically Progress - Danger.
  5. Create an action plan for the first few routes (if we can afford it) by:
    1. Creating a graph of possible actions by...
      1. Creating a node for each initial action.
      2. As nodes are created, assign them a score and cost. Score being progress to the next platform in the path. Cost being damage taken.
      3. 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.
      4. Iterate through the nodes, choosing the most promising each time until the goal platform is achieved.
    2. Hopefully, by using a heuristic during the creation process, we can avoid chewing up 20Gb of memory not to mention the processing time.
  6. Choose the best of these plans, Total Score - Total Cost.
  7. 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,

Nathan


Personal Page: http://www.nathanrunge.com/     Company Page: http://www.ozymandias.com.au/


#9 DrEvil   Members   -  Reputation: 1105

Like
2Likes
Like

Posted 16 May 2013 - 08:28 AM

That makes sense. Most defense type of games have some sort of 'slow down enemies' type of buildable. I'm not entirely clear on how that will be accounted for with jump links without cheating the velocity in some way. You could justify using a consistent jump velocity perhaps by having a crouch and jump animation if they get to the link without the proper speed or something rather than an unanticipated velocity adjustment. Then it could become a gameplay element, since slowing them down not only gives them more time of vulnerability but will also force them into taking a slower version of the jump.

When doing arbitrary jumps I agree it is easier to work with jumping and velocity in terms of separating the components. Pressing jump may set a y velocity and such in order to get the correct physics behavior of using the entities current horizontal velocity. When it comes to planning though, unless you want an explosion of complexity and runtime computation to consider a fluid and wide range of velocity, you will need to use either fixed jump velocities or discrete jump velocity values to limit the search space. In that context for the AI it will likely at some point involve a setting of both components of the velocity to match the preprocessed velocity expectation of the jump links. When they are of close enough velocity to fake it that way as part of a run, or if you want to hide more widely disparate velocity in a prepatory animation and such is just decisions about how you sell the velocity change to the player. You could include both max speed and maybe max speed * 0.5 in the precalculation of jump links so that you get jump links of different thresholds. I would personally try to avoid doing that, especially as you mention there will already be separately calculated jump link sets with regards to the jump characteristics of different AI types.

As far as when/where to precalculate, I would build the connections after the platform segments, primarily because the platform segments act as the simplest links in the navigation graph. If the target platform is a mobile platform or something with limited computational resources, I would try to code the system in such a way that during the build phase the platform segments and jump links would be patched in incrementally as obstacles are placed or removed. It shouldn't be necessary to rebuild the entire map, and if it is computationally more than you want to wait for when the build phase ends it would be best to be doing it during the mostly idle build phase. When an obstacle is placed you clip its extents from the platform it was placed on(ie split the platform), mark any jump links that it overlaps as disabled, and if it can be jumped on top of, calculate new jump links to the new platform on top of the obstacle. You would only need to recalculate the physics trajectories for jump links whose horizontal span overlaps the new obstacle, so incrementally patching the navigation as things are added and removed should be relatively easy and spread the load across the build phase. The bulk of the navigation graph and jump links can be calculated with the static environment during initial load, and links marked as disabled from dynamic object overlap or blockage of trajectory in an incremental fashion as objects are removed or added. You could even cache on any disabled jump link the obstacles that contribute to its blockage, such that at runtime when any object is destroyed it would be trivial to reenabled affected links.

Yea I was talking about the possibility of using a simple occupancy grid in order to reduce the number of actual collision tests performed as part of the trajectory test, since that will be the expensive part.

The break downs sound good. Just for more detail, the jump velocity would be part of the meta data for a jump connection for use by any AI that end up taking the link.

As far as the runtime is concerned, danger can be reflected in cost modifications to the links of a standard A* search. For instances, maybe when someone dies or is damaged, you would increase the weight of the nearest edge to that guys position in the form of an additive value that gets added to the cost of the edge, and during the update loop you would tick down the additive at some rate so penalties will sort of renormalize over time in the influence map sort of sense. For building the path, I would always start from the platform directly undernearth the AI. During jumps you want the guy to 'steer' to the landing point(if there is air control) so you would want to avoid updating the path during a jump, but while not jumping, grab the platform below the AI and pathfind on the platform+jump links graph.

Using the platform segments as nodes of the graph and jump links as links of the graph I wouldn't expect the pathfinding itself to be very computationally expensive or even for the graph to be all that complex, and even if you pathed to the end of the level. The platform segments are nodes in the sense that they are branch points to jump links, but are themselves treated as links as well because you probably want to include in the search weightings with respect to the AI position and remaining length of the segment(ie project AI point along path, use that position to jump links as initial branch weightings). Even though there will be quite a few jump links, in the context of a particular AI they will only look at the ones applicable to their type, and there are probably only a few jump links at end end of a platform. You could reduce the jump links during the generation phase by taking each set of jump links of a certain type between the same source and destination platforms and combine them into a single one based on some criteria, like keep the one with the takeoff position furthest along the start platform, or the mid range jump segment, or keep them and group them into a jump set by start and end platforms and pick one of them appropriate to the context of the specific search I am performing. Maybe as simple as picking the closest one that to the right of me, to bias moving forward, or maybe skipping the next if there are ones after if they don't meet a movement speed threshold to give them some acceleration time but still must take the last link as a last resort. In order to frequently take into account dynamic link weightings I might even recalculate the path any time the AI platform changes, although it might be desirable to do it more often if you have long platform segments that you want to be responsive to weight changes even while a group of AI are on the platform.

I'm not sure what you mean about shifting the simulation to the preparation phase. Do you mean exclusively? Or just for preprocessing jump links in a physically accurate way as I described?

With regards to mobile obstacles, I guess it depends on the nature of the mobile obstacles. What sort of mobile obstacles are you talking about? Is this different from moving platforms? Are they still restricted from being put a tile away from the edge? Are they purely impassable? I would be a bit worried that if the player had access to mobile obstacles it would be easy for a player to park them over jump links and cut off the AI. Static obstacles, such as those placed in the build phase, can be validated and ensured that there is always a path to the end of the level, in the same way top down free building tower defense games(such as fieldrunners) use pathfinding to ensure there is a path to the destinations and not allow you to place objects that would block off the path. Doing that validation essentially requires that you do incremental navigation building during the build phase not just when items are placed and removed, but during placement to draw them in red or with an X over or whatever to disallow maybe unforseen edge cases where it may be possible to block the path to the goal.

Mobile objects that must be traversed via jumping in the same way that jumping between platforms must be navigated is going to mean doing those expensive calculations at runtime to calculate jump traversals over the moving objects whenever they move. That might get prohibitively expensive, but if that was a route you wanted to take, at the high level I would start with the following. If I were making this game, and assuming mobile obstacles are going to play a significant role, I would probably allow my jump preprocessor to calculate essentially all jumps in the level, even jumps that start and end in the same platform, because then you only need disable and enable overlapping jump links to mobile obstacles. I would be concerned however with the gameplay implications of mobile obstacles, players blocking off all jump links, to ensure the AI had adequate fallbacks that the player couldn't game them easily. This obviously balloons up the memory requirements for the jump list, but those can be packed efficiently and the memory cost will more than make up for the elimination of calculating runtime links, and your game world seems easily small enough that this shouldn't be a huge data set. Generally a more complicated graph would also make the pathfinding more expensive, but there are trivial optimizations you can use in that area as well to avoid branching along certain links. For example, if you sort the jump links for a given platform such that all the jump links that connect to itself are at the end of the list, the pathfinder can break when expanding if there are no mobile obstacles on the platform, because those links can be thought to have the express purpose of avoiding dynamic obstacles.

So far all this stays firmly in the camp of a navigation graph and mostly standard A*, albeit on a dynamically updated graph. Pathfinding is a planner in a way, but I don't think we are talking about a planner in a stricter sense that I think you mean(as you mentioned GOAP)



#10 NathanRunge   Members   -  Reputation: 541

Like
1Likes
Like

Posted 16 May 2013 - 08:38 PM

Simplification

I think, for the moment at least, we're looking to simplify the problem. As such, we're:

  1. Eliminating the possibility of moving platforms.
  2. 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.

 

Jump Arcs

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.

 

Precalculation

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.

 

Path Creation

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?

 

Mobile Obstacles

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.

Attached Thumbnails

  • Hazards.png

Edited by NathanRunge, 16 May 2013 - 08:38 PM.

Personal Page: http://www.nathanrunge.com/     Company Page: http://www.ozymandias.com.au/


#11 DrEvil   Members   -  Reputation: 1105

Like
1Likes
Like

Posted 17 May 2013 - 07:53 AM

Actually let me restate and show some visuals in case I messed up the explanation in a prior post. It's not that all jump links need trajectories of the same horizontal x component, it's that whatever x,y velocities that were precalculated for a particular jump need to be the ones used at runtime. The values of the velocity components at these jumps will vary quite a bit. I'm not even sure it's possible to do all the velocities of the game with a fixed jump height. When you think about platformers from the players perspective, the player often has control over their jump height such as in the form of how long they hold down the jump key. Looking at your pictures, the implication is that there is the possibility for very high jump arcs, but contrasted with the small platforms and finer detail of the level, you probably couln't use that same jump velocity over that large gap to get out of that hole in the first picture.

Also to clarify about jump links. At first I was picturing calculating only jump links between separate platforms, to and from those unbuildable buffer regions which are non blockable, because with limited information it didn't seem necessary to calculate jump links within the same platform, because running is probably preferred. With the introduction of mobile obstacles though, it might be preferrable to calculate many more jump links that even connect within the same segment such that there is a bunch of jumps internal to a single platform even that can be disabled via an overlap test with the mobile obstacles and others used to get around those obstacles inside the context of a single platform link. Without calculating this denser set of jump possibilities and paying an extra memory cost, you'd have to calculate the jump trajectories and validate them at runtime which could be worse for performance. If you come up with clever ways to optimize the trajectory collision tests though it might be viable to do them at runtime. The trickiest part I think about precalculating these 'mobile object avoid' jump links is that if you have wildly different sized mobile obstacles, you may need to calculate a number of different set of jump velocities. In theory if obstacles can move you have no guarantee about what span of a platform may be obstructed, so there would need to be a good set of jump velocities, big and small jumps, to have reliable options. Frankly I'd be concerned that it may still be breakable more often than is comfortable. I have no idea of the scale of your obstacles, but for example, the 3rd pic shows some intermediate jump links for small jumps that may only help get over small obstacles. You may calculate these jump links with respect to your largest obstacle or based on a max size that smaller obstacles might clump up as, but it's probably a good idea to still build them along the platform at similarly small intervals so there is plenty of takeoff and landing points.

 

g1.png

 

g2.png


As far as mobile obstacles are concerned, in the context of a 4th dimensional planner that uses time as one of its parameters, knowing the pattern of a movable obstacle is very important. To my knowledge, this sort of planner is best way to properly plan future moves, but this technique is very expensive. If it were to attempt to calculate an optimal path through an obstacle like that swinging trap, the search would branch in such a way that each node of the search would essentially represent carry with it a world state along with the predicted AI position at that time in the world state. This might just be a world game time of some time in the future, and internal to the search you'd have to essentially set up a temporary state for the world, such as where in the obstacles pattern they are at that time and validate the AI position against those predicted object states. This may result in a plan that involves stopping and waiting depending on the current state of the trap. It's essentially the implementation of asking questions like, "if I go now will I get hit", "if i wait some period of time will i get hit", "if i go now i can miss one obstacle but ill hit the next, so i need to wait until i can make it through both". Obviously the search space for this sort of decision making can be huge and to my knowledge this degree of complexity tends to be avoided at runtime.

With that in mind, I would probably tackle the logic for how to traverse each obstacle in isolated parts specific to the obstacle to keep things simple and cheap. In the image, suppose the build footprint of the obstacle were the red span, and the 'danger' footprint were the green span. I've approximiated this value just by eye balling the hammer trajectory, and the end points are about the height where their bounds just clears the height of the AI. There could potentially be multiple hazard segments for AI of different heights if you wanted them to stage and continue more appropriate to their physical characteristics. Essentially I would perhaps treat the differences on the ends as wait points or staging points. The AI will wait there if the current state of the obstacle is not safe. Safe is obstacle specific but in this case I would do something simple like, if the left extent of the hammer bounds is >= the right side of my bounds, and the its x velocity is positive(moving right), I can go. This would be a simple way for the AI to wait when its swinging towards them, and go at the opportune point that would cause them to chase the hammer through on its retreating swing, like when we used to run under people on swing sets. More complex mathematical evaluation would be necessary I think to analyze the feasibility of traversing this sort of obstacle in other parts of its pattern. This simplistic technique is just capitalizing on the one situation where one has the most time to get through it. At a high calculation expense, a planner should be able to find other solutions if there are some, at

the cost of essentially trying a bunch of different timings.

 

obs1.png


Finally, one last simple quicky you probably already thought about. I'm speculating a bit but it looks like those rocks are irregular in the sense that they don't represent a boxy continuous horizontal span with the surrounding ground. If one were to land on the sloped parts of the rock I'm not sure if you are planning to slide them down to the ground or if the rock is indeed boxy and they might just float, but regardless of which it is, you should probably make it a point to represent absolutely every navigable possibility in the map with some sort of line segment for navigation purposes. If slopes like that involve controlled slides down to the ground, they should probably be represented as a 'slide' segment, such that the weighting on that slide can be accounted for in the pathing. For example, maybe the slide speed makes sliding down less optimal than a jump, the pathfinder can find that. Alternately, perhaps a necessary jump can only be reached part way down a slide link, it will find that too. Maybe its faster to jump at the top of a long slide, land in the middle of the slide segment, and continue sliding, or jump again. This will all be possible so long as it is represented, and if you don't want that sort of behavior it's easy to disable jump generation from slide segments. Anything with navigable possibilities should have segment representations in the navigation. This also ensures that if for some dynamic reason an AI is knocked around a bit, there is no possibility outside of being knocked in a death pit, that they will end up over some part of the level that doesn't have navigation under it.

 

 






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS