Pathfinding API in script

[Crimson Wizard]

I had a sudden moment of enthusiasm today, so wrote a draft for the basic Pathfinding API...
(To be fair, this is not a sudden idea, we discussed this on github a while ago.)

PR: https://github.com/adventuregamestudio/ags/pull/2441
Download for a test (based on AGS 4): https://cirrus-ci.com/task/5429664145997824
Last Updated: 14th June

The Pathfinding api lets user to use AGS internal pathfinder in script. This allows to calculate paths on the current room's walkable areas, but also lets to create a pathfinder object with a custom mask (from a sprite).

The new API is following:

Code: ags

builtin managed struct Pathfinder {
  /// Tries to find a move path from source to destination, returns an array of navigation points.
  Point*[] FindPath(int srcx, int srcy, int dstx, int dsty);
  /// Traces a straight path from source to destination, returns the furthermost point reached.
  Point* Trace(int srcx, int srcy, int dstx, int dsty);
};

builtin managed struct MaskPathfinder extends Pathfinder {
  /// Creates a new MaskPathfinder, initialized with the given 8-bit mask sprite
  static MaskPathfinder* Create(int mask_sprite); 
  /// Assigns a new mask to this MaskPathfinder
  void SetMask(int mask_sprite);
};

Pathfinder class is a parent class that provides generic methods, unrelated to how the pathfinding works. User cannot create objects of this class directly.
MaskPathfinder is a child class that implements a pathfinder based on 8-bit masks.

**IMPORTANT**: MaskPathfinder is currently disabled in script, because AGS does not let create or import 8-bit sprites in hi-color games. There's a separate task planned to resolve this problem. After that is done, MaskPathfinder may be re-enabled.

And this to the Room struct:

Code: ags

struct Room {
  <...>
  /// Gets this Room's Pathfinder object that lets find route around walkable areas.
  readonly Pathfinder *PathFinder;
}

Note that the Room returns a pointer of parent type Pathfinder, but it creates MaskPathfinder internally. This is done to restrict user from changing the room pathfinder's mask, because this pathfinder object is meant to represent actual room's walkable areas.

Then new variants of Walk and Move that accept array of Points:

Code: ags

/// Moves the character along the path, ignoring walkable areas, without playing his walking animation.
function Character.MovePath(Point*[], BlockingStyle=eNoBlock);
/// Moves the character along the path, ignoring walkable areas, automatically playing his walking animation.
function Character.WalkPath(Point*[], BlockingStyle=eNoBlock);
/// Returns the moving path of this character, or null if it's not moving
Point*[] Character.GetPath();
/// Moves the object along the path, ignoring walkable areas.
function Object.MovePath(Point*[], int speed, BlockingStyle=eNoBlock);
/// Returns the moving path of this object, or null if it's not moving
Point*[] Object.GetPath();

In these MovePath and WalkPath functions it is possible to pass a result of Pathfinder.FindPath, but also possible to just make your own path the way you please. GetPath() functions return the copies of the current path. If moving order changes, the previously returned array becomes obsolete (and not automatically updated, of course).

The working example script:

Spoiler

WARNING: player Character must be set Solid = false for this script to work! otherwise paths won't be found, because they start inside the Character's blocking area.

Code: ags

DynamicSprite *pathspr;
DynamicSprite *mask_copy;
Overlay *pathover;

function on_mouse_click(MouseButton button)
{
	if (pathover == null)
	{
		pathspr = DynamicSprite.Create(Room.Width, Room.Height);
		pathover = Overlay.CreateRoomGraphical(0, 0, pathspr.Graphic);
	}
	
	if (mask_copy == null)
	{
		mask_copy = DynamicSprite.Create(Room.Width, Room.Height);
	}
	
	DrawingSurface *mask_copy_ds = mask_copy.GetDrawingSurface();
	DrawingSurface *mask = WalkableArea.GetDrawingSurface();
	mask_copy_ds.Clear(30);
	mask_copy_ds.DrawSurface(mask);
	mask.Release();
	mask_copy_ds.Release();
  
	Point *goal = Screen.ScreenToRoomPoint(mouse.x, mouse.y);
	Pathfinder *finder = Room.PathFinder;
	Point *path[] = finder.FindPath(player.x, player.y, goal.x, goal.y);
	Point *trace = finder.Trace(player.x, player.y, goal.x, goal.y);
	
	DrawingSurface *ds = pathspr.GetDrawingSurface();
	ds.Clear(COLOR_TRANSPARENT);
	ds.DrawImage(0, 0, mask_copy.Graphic, 50);
	
	if (path != null)
	{
		for (int i = 0; i < path.Length; i++)
		{
			if (i > 0)
			{
				ds.DrawingColor = 1;
				ds.DrawLine(path[i - 1].x, path[i - 1].y, path[i].x, path[i].y);
			}
			ds.DrawingColor = 4;
			ds.DrawRectangle(path[i].x - 1, path[i].y - 1, path[i].x + 1, path[i].y + 1);
		}
	}
	
	if (trace != null)
	{
		ds.DrawingColor = 12;
		ds.DrawLine(player.x, player.y, trace.x, trace.y);
	}
	
	ds.Release();
}

[close]

Illustration of running above script:
(clicking around calculates a walk path from character to a certain point, and draws that path on screen)



Possibly we'd also need extra property or argument for the Pathfinder returned by the Room, which tells to ignore solid objects and characters, because right now they may unexpectedly "get in a way" (both literally and figuratively).
**UPDATE:** this problem is left for the future. At the moment the workaround is to manually toggle Solid property of wanted objects or characters before calling FindPath.

[Crimson Wizard]

Updated with the new Move and Walk functions:

Code: ags

/// Moves the character along the path, ignoring walkable areas, without playing his walking animation.
function Character.MovePath(Point*[], BlockingStyle=eNoBlock);
/// Moves the character along the path, ignoring walkable areas, automatically playing his walking animation.
function Character.WalkPath(Point*[], BlockingStyle=eNoBlock);
/// Moves the object along the path, ignoring walkable areas.
function Object.MovePath(Point*[], int speed, BlockingStyle=eNoBlock);

Download for a test (based on AGS 4):
https://cirrus-ci.com/task/4605831403012096

[Retro Wolf]

So could you use the DrawingSurface functions to draw shapes onto a surface using code, then use that as your walkable areas?

[Crimson Wizard]

So could you use the DrawingSurface functions to draw shapes onto a surface using code, then use that as your walkable areas?

Yes.
OTOH you already can dynamically create walkable areas in the room, since AGS 3.6.0:
https://adventuregamestudio.github.io/ags-manual/Globalfunctions_Room.html#getdrawingsurfaceforwalkablearea

[Retro Wolf]

Cool!

[Crimson Wizard]

Added couple of more functions:

Code: ags

/// Returns the moving path of this character, or null if it's not moving
Point*[] Character.GetPath();
/// Returns the moving path of this object, or null if it's not moving
Point*[] Object.GetPath();

These return the copies of the current path. If moving order changes, the previously returned array becomes obsolete (not automatically updated, of course).

 I have a thought about adding something that returns a more sophisticated object, which describes not only the current path, but also speeds and current position on this path, but perhaps I should do this as a separate task.

Updated download for a test (based on AGS 4):
https://cirrus-ci.com/task/5429664145997824

[Crimson Wizard]

This is a separate update which adds RepeatStyle and Direction parameters to MovePath and WalkPath functions:
PR: https://github.com/adventuregamestudio/ags/pull/2444
Download: https://cirrus-ci.com/task/4873137047732224

Now it lets to do patrolling without repeatedly_execute:

Code: ags

Point* path[] = new Point[3];
path[0] = new Point; path[0].x = 100; path[0].y = 100;
path[1] = new Point; path[1].x = 200; path[1].y = 100;
path[2] = path[0]; // make it circular

cGuard.WalkPath(path, eNoBlock, eRepeat);

[Crimson Wizard]

All the above is now a part of AGS 4.0 Alpha.
https://www.adventuregamestudio.co.uk/forums/ags-engine-editor-releases/ags-4-0-early-alpha-for-public-test/msg636663912/#msg636663912

[Crimson Wizard]

In regards to a custom MaskPathfinder, here's a new PR which allows to create and load 8-bit sprites in 32-bit games keeping their 8-bit format (which was not possible to do in AGS, because everything got converted to the game resolution):
https://github.com/adventuregamestudio/ags/pull/2455

After this the MaskPathfinder could be re-enabled.

This is rather straightforward in terms of coding, but at the moment the biggest question is the form of the options in script commands (as explained in the ticket).

[Crimson Wizard]

MaskPathfinder is now the part of AGS 4 too, and AGS allows to import and load sprites in 8-bit as an option (without auto converting them to game's default format), so it's possible to have pathfinding over custom 8-bit bitmaps in script without any relation to the room.