Problem 4.2 RPG

Master / Vertiefung Künstliche Intelligenz
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Problem 4.2 RPG
I somehow can’t wrap my head around this problem. I will try to describe what is unclear to me:

  • How does the player control his character? Does he just press a button and the character moves from the start to the goal (red to green in the picture)?
  • Are diagonal steps allowed?

I thought that A* is an Algorithm used to solve offline problems?

Sorry, but I just basically don’t understand what the AI part of this game does. If the player has full control over where the character moves (as in most RPGs I know) an AI computing the fastest way from A to B would only be used as an navigation device (aka a convenience feature) and this AI would not need information about the players’s visible area.

3

Think of something like RTSs, where you just select a character and right-click where you want him to move

Let’s say no :slight_smile:

In this case it makes absolutely no difference - in either case the goal is to find a path from A to B. The distinction Online/Offline only makes sense in the presence of adversaries.

It wouldn’t need it if you want to be able to abuse the navigation device to find optimal paths between unexplored areas. That would be bad game design though.

4

Ok that was helpful, but unfortunately I still wonder how this works.

The player is on red, he rightclicks on green (even if green is not visible for him).
The character moves to every cell that is expanded by A* as it is being computed?
How is the visible radius used by A*?

…I think should play Baldurs Gate II again…

5

The way I interpret it is this: Since there’s a visibility radius, A* can not expand nodes any further than up to that radius; meaning a successor of the starting point needs to be picked at that point (and the character moved), allowing to expand more nodes in the direction the character moved.

But feel free to interpret this differently. Part of - or, actually, rather the main point of - the exercise is for you to model the game description as an A*-search in the first place, so in a sense I’ve given you part of at least a possible answer :wink: