• Create Account

# NathanRunge

Member Since 08 Feb 2008
Offline Last Active Mar 05 2014 05:40 AM

### In Topic: 2D Platformer AI

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.

### In Topic: 2D Platformer AI

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

### In Topic: 2D Platformer AI

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.

### In Topic: 2D Platformer AI

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.

### In Topic: What to do with articles of opinion

18 April 2013 - 04:30 AM

I think the majority of gamedev readers would prefer most articles to focus on practical fact rather than opinion, with a number of sites such as GamaSutra providing excellent avenues for distributing opinion. That said, I don't think that this should preclude articles that present an opinion. I support clearly identifying these articles, and an author should declare the context surrounding their opinion.

I think the most important determining factor for the suitability of an opinion article is its substance. Articles presenting an opinion should be presented, effectively, in essay format. The author should be introducing the topic and context. They should then present a well supported argument for the position, complete with examples or citations, informally or otherwise. It comes down to presenting an opinion that can be justified and evidenced.

If an opinion is explained, then it can be discussed intelligently and it practical lessons can be taken. If an opinion is expressed without context or evidence, it effectively becomes a soapbox or rant, which have their place in blogs.

An example I may offer is a discussion on piracy. These discussion happen often and they're rarely intelligent or worth-while. If someone presents a lengthy opinion arguing that piracy is destroying the industry it benefits no-one and will quickly devolve into back and forth. If someone puts forward their opinion that piracy is a more significant issue than we consider it to be, complete with citations on sales and the results of various studies, possibly summarising with a proposed approach, then there are details that can be discussed and lessons may be learnt. It'll inevitably turn into bickering anyway, but it at least has merit.

PARTNERS