Trick or Treat Adventure Pathfinding

In my efforts to post a Trick or Treat Adventure update every week, here is a more technical deep-dive into one of the improvements for the Steam release...

PATH FINDING!

In the original web version of the game, it was pretty frustrating to get around because you would run into "non-walkable" areas all the time and there was no logic to smartly navigate your character around a room. And if you clicked something interactive, but weren't close enough or lucky enough to be able to walk right up to it, you'd get an annoying message telling you to get closer.

In the new version, we've implemented better path finding! You might be thinking: "Wow, you must have used some advanced pathfinding algorithm like A*!" But you'd be wrong... DEAD WRONG!

The way we did it is actually based on an old post by Aaron Worral about how he did pathfinding in Johnny Rocketfingers 2! Basically, you put down (as named MovieClips) some "numbered nodes" in strategic walkable areas of the "room." These nodes can all "see" each other (direct line of sight) without running into non-walkable space. They're numbered, so they form a kind of "ordered backbone" to the walkable area of the room. You only need enough nodes such that every walkable area of the room can be seen by at least one node without hitting the non-walkable area.

Here they are overlaid on the kitchen background/room from the game. The transparent red is the "antiwalk" (non walkable) area of the room. You can see how it feels like the room's "spinal cord" and each vertebrae can allow access to areas of the room it can see directly (direct line of sight).

Then the rest of the logic is pretty simple:

1. On a click, can the player reach the destination without hitting antiwalk? Just go directly there.

2. Is the destination blocked? Ok, get the node nearest the player and the node nearest the destination. Figure out if the node nearest the destination is greater than or less than the node nearest the player (this tells you which direction on the spine you need to move). Move the player to the spine node nearest him.

3. Navigate along the spine (either increasing or decreasing node number based on step 2 above).

4. You can either wait 'til you reach the node nearest the destination and then walk to destination, OR you can just constantly check if the destination is "in direct line of sight" with the player, and as soon as it is, walk to the destination.

It's really that simple! Of course you need to write some code that uses a while loop to do the direct line of sight checking (using trigonometry to crawl along the hypotenuse of a triangle in small increments to see if you hit the antiwalk at any point). That's probably the most "complex" part, but you can do it!

The code might look something like this (wow Actionscript 2.0!!!):

// determines if player x,y has a direct line of sight to a destination point
// without hitting the antiwalk
// allDots = [] // uncomment this to visualize what this code is doing
function hasDirectLineOfSight(x, y, who) {
	var distx = x - who._x;
	var disty = y - who._y;
	
// hypotenuse of the triangle!
	var hyp = Math.sqrt(distx * distx + disty * disty);
	
	var dx = distx / hyp; // 1px increment in desired direction for x
	var dy = disty / hyp; // 1px increment in desired direction for y
	
	var startx = who._x;
	var starty = who._y;
	
	for (var i = 0; i < hyp; i += 6) {
		startx += dx * 6;
		starty += dy * 6;
		
		/*
// use this if you want to actually visualize what this code is doing...
		var d = wrap.attachMovie("vtest", "vtest" + i, i + 8888);
		d._x = startx;
		d._y = starty;
		allDots.push(d);
		*/
		
// checking if we're hitting the antiwalk
		if (wrap.aw.hitTest(startx + wrap._x, starty + wrap._y, true)) {
			//trace("hit antiwalk!");
			return false;
		}
	}
	
	//trace("clear!");
	return true;
}

Hopefully that made sense!

Here's the final result, sooooo much nicer to play now!

Thanks for dropping by, we're very excited to keep adding new stuff and improvements to this game for everyone here on Steam!

--Nick