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.

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.

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.

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.

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.

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.

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.

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

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)

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.