gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Action Based Pathfinding

#103890 - sgeos - Mon Sep 25, 2006 5:02 am

It seems to me that interesting (platformer) pathfinding could be achieved with direction/action pairs. (This is really only a small variation of standard directions.) If you treat things like the edges of platforms as key points, then you could get to the platform above it with something like "jump 5, right". If my critter only has jump 4, then clearly he can't reach the platform- although I could write AI that tries regardless.

Code:
class Critter
{
  privite type_t mMisjudge;  // chance of AI messing up

  public Boolean canDo(Action pAction)
  {
    ...
  }
}

I guess that the dumb autogeneration algorithm would be something like this:
Code:
for (entireMap)
  if (edge)
    addToKeyPoints()

for (a = allKeyPoints)
  for (b = allKeyPoints)
    for (allActions)
      if (doesConnect(a, b, action))
        addToConnetionTable(a, b, action)

Your table will consist of structs that look something like this:
Code:
struct
{
  Point from;
  Point to;
  Action action;
}

If you don't allow double entries, you could make either "from" or "to" implicit by treating it as an index.

"Action" assumes a ROM based first step table. You could, of course, use a list of actions instead.

-Brendan

#103893 - sajiimori - Mon Sep 25, 2006 5:47 am

Key points aren't just ledges -- they can be otherwise boring-looking points that just happen to have access to overhangs by jumping upward. If you imagine a gap in the ceiling that you can jump through, there's a key point below the gap.

I can think of 3 solutions to that complication, off the top of my head:

- Place and connect key points by hand and tag them with appropriate actions. (This approach has been used on some games at my studio.)

- Write a "seek" algorithm which dynamically generates a plan for getting from point A to point B, including jumping over gaps and onto ledges. (I use this approach myself.)

- Write a "seek" algorithm, but execute it many times as part of the build process and write all the useful results to the ROM.

#103914 - keldon - Mon Sep 25, 2006 11:12 am

Do you aim to create AI that can immediately play a level in real time that includes moving ledges/platforms and enemies in real time, or AI that can examine a level and eventually find a solution?

#104012 - sgeos - Tue Sep 26, 2006 12:04 am

sajiimori wrote:
Key points aren't just ledges -- they can be otherwise boring-looking points that just happen to have access to overhangs by jumping upward. If you imagine a gap in the ceiling that you can jump through, there's a key point below the gap.

"Dumb autogeneration". I think you could find all key points by starting with platform edges. You'd need to trace from each key point to "where ever" using each action and then mark all of those key points. Although this might not work. It would bloat the key point table and useless entries would need to be removed.

sajiimori wrote:
- Place and connect key points by hand and tag them with appropriate actions. (This approach has been used on some games at my studio.)

Human brute force approach. With testing, this will always work for any map. If you have trained level designers, fantastic- go for it. If not, this will be expensive. I like to avoid manual when possible.

sajiimori wrote:
- Write a "seek" algorithm which dynamically generates a plan for getting from point A to point B, including jumping over gaps and onto ledges. (I use this approach myself.)

What does a typical seek algorithm consist of?

sajiimori wrote:
- Write a "seek" algorithm, but execute it many times as part of the build process and write all the useful results to the ROM.

As above only you use a LUT or equivalent.

keldon wrote:
Do you aim to create AI that can immediately play a level in real time that includes moving ledges/platforms and enemies in real time, or AI that can examine a level and eventually find a solution?

If you can do one, you can generally do the other if you have enough cycles. If you want a ROM based LUT that handles moving platforms, you'd have to add criteria to you action. Static points can "always" be moved to. Moving objects can be moved from "if" such and such is true:
    the platform has a horizontal distance from you of less than 5
    the platform is (not) in spike mode (jumping takes time)
    etc
-Brendan

#104013 - keldon - Tue Sep 26, 2006 12:11 am

What are all of the constraints? Or are you going to base the constraints of the levels on the capabilities of the AI?

For example you could have more complicated levels with multiple routes, or simply alternate platforms that make jumping easier/harder or something of that nature. You can have hills, ice, spikes on edges of walls.

Do you want your AI to be aware of parts of the level that are out of view? If not then isn't the goal of the AI simply to progress to the next ledge safely? Does this AI aim to eventually get better, by for example saving its progress/ information?

#104016 - sajiimori - Tue Sep 26, 2006 12:48 am

Quote:
I think you could find all key points by starting with platform edges. You'd need to trace from each key point to "where ever" using each action and then mark all of those key points.

For my example, you'd need to trace from every point in the map (not just key points) to every key point, which would cause the point under the ceiling gap to be marked with a jump.
Quote:
Human brute force approach.

How about the I-don't-have-time-to-implement-and-debug-a-complex-algorithm approach? ;) It totally depends on the situation.

I use the term "seek" to refer to uninformed pathfinding algorithms that work purely by examining map data. I implemented mine by doing traces that follow slopes and look for cliffs and walls. Given a start and end point, it tries to close the gap between them by following the floor toward each other. It stops when the traces meet or one passes over the other. If the start trace goes under the end trace, you have to jump up.

For tile-based maps, such traces typically amount to looping over spans of tiles and stopping when you hit something interesting.

#104068 - keldon - Tue Sep 26, 2006 10:31 am

P.s., Here is an example of something that gives the AI a big decision. And if it knows of the level before hand then it will immediately know to jump on the ledge, otherwise it will have to backtrack on his steps.

Code:
       _______
   ___/
__________      ___

#104121 - tepples - Tue Sep 26, 2006 6:13 pm

Your diagram is 19 tiles wide. Assuming you're using 16x16 pixel metatiles, as a lot of NES and Super NES games used, that's more than a screen width. Are you planning on having the AI enemy chase the player through a whole level, or just the typical AI that chases the player through the half a screen distance between the player and the enemy?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#104122 - sajiimori - Tue Sep 26, 2006 6:16 pm

Yeah keldon, it seems to me that regardless of whether you want to precalculate all pathfinding or do it at runtime, you're going to need a seek algorithm that's capable of seeing that you can jump from the lower left to the left side of the upper platform (and vice versa), and from the right side of the upper platform to the lower right (but perhaps not vice versa).

#104140 - thegamefreak0134 - Tue Sep 26, 2006 7:26 pm

It seems like you could put a key point at the beginning of the ledge that basically blocks the gap off if the enemy cannot jump it to overcome this situation. Then, if the player is already on the other side of the gap, the AI simply jumps on the ledge and that is that. Of course, if the player can jump the gap, you could potentially \\\"lure\\\" the AI into a trap that would make it either backtrack or jump to its doom...

-gamefreak

PS: I don\'t know the extent of this topic enough, but would a path-finding routine be able to trace the entire path to a certain location within a frame? If the level were simple enough, could this be performed every frame for three particularly complicated computer AIs?
_________________
What if the hokey-pokey really is what it's all about?

[url=http:/www.darknovagames.com/index.php?action=recruit&clanid=1]Support Zeta on DarkNova![/url]

#104150 - tepples - Tue Sep 26, 2006 7:37 pm

You only really have to recompute an agent's path once every 60 frames or so, to simulate agents' reaction times.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#104152 - thegamefreak0134 - Tue Sep 26, 2006 7:42 pm

I see. I was talking about more of a fighting stle game, but one in which there is still a small \'evel to move around. OK, ok, I dont know where to start with the smash bros AI, Ive said it, alright? Sheesh... Anywho, it was just a thought. Dont worry about it.
_________________
What if the hokey-pokey really is what it's all about?

[url=http:/www.darknovagames.com/index.php?action=recruit&clanid=1]Support Zeta on DarkNova![/url]

#104154 - sajiimori - Tue Sep 26, 2006 7:45 pm

thegamefreak0134, we know that it's easy enough to hand-tune graphs on a per-level basis. The hard part is writing algorithms that can decide on their own.

In graph-oriented terms, you either don't create an edge that goes under the platform, or you create one but mark it with a tag saying the character must be able to do a long jump to traverse it.

If you don't want the AI to jump to its doom, you can code it so it won't.

My pathfinding code breaks up work across multiple frames. A character will sometimes pause momentarily to decide how they'll get to their destination. The complexity of a navigate operation can increase the delay, but it doesn't significantly affect CPU usage per frame.

#104164 - thegamefreak0134 - Tue Sep 26, 2006 9:02 pm

Oh. I see. And I supppose I could have my characters plotting their next moves while the animation for the previous one was happening. OK, I like it. I\'m going to shut up and code some now.

Sorry for interpreting the question incorrectly...
_________________
What if the hokey-pokey really is what it's all about?

[url=http:/www.darknovagames.com/index.php?action=recruit&clanid=1]Support Zeta on DarkNova![/url]

#104177 - keldon - Tue Sep 26, 2006 11:03 pm

Ok, from what you have said I believe the following to be true:
- there are no obstacles like spikes, or enemies that can kill your ai 'Critter'
- the goal of the AI is to reach the destination
- there are no moving ledges

I would develop two parts of AI:
- identifying key points by reading map
- perform reachability with near neighbours
- combine reachability with key points to create a reduced graph
- play the rest by ear on how you handle the path finding + planning + execution of plan

EDIT: Yes I know that's not two parts.

EDIT2: Yes I know, I could have just edited the 'two parts'

EDIT3: Yes, I know I still could have. Ok, that's enough edits ^_^

#104219 - sgeos - Wed Sep 27, 2006 6:10 am

For a smash brothers clone I'd actually hand place key points. You have a small number of small maps. For a game with the data load of Super Mario World, I'd want an automated solution.

-Brendan