n3wt0n!

I could have sworn I’d already posted this graphic.

Still, this is the “accessible area map” implemented in SpaceFight!. If you visit the prototype page you should be able to give it a try. It needs some improvement. It’s a resource hog, especially where there are a lot of wall tiles side by side. And the polygons haven’t joined together as I’d hoped, as you can see by the multitude of ‘pie slices’.

After I’ve reduced the inefficiencies of the algorithm and made the accessible area mapping look good, I get to work on the path-finding. Something to map points of the shortest distance between the player’s location and where the player wants to go within the accessible area. And to display that path. I’m sure it will be all kinds of fun. Seriously. It was all kinds of fun getting the accessible area map to the point it’s at now.

The prototype has always been available here but this is a reminder in case you were unaware. However, that link won’t be the permanent location of SpaceFight!. It will eventually have its own proper home. Probably on another domain I recently purchased and set up. Mystery! Kind of.

I wrote in my previous post that my idea would make sense once I got it working.

The purpose of this “Accessible Area” map is for the game, SpaceFight!. The orange area represents the places that the player character can reach given a certain amount of time. The algorithm works something like the following:

1. Build a list of visible wall nodes (corners) within a range around the player
2. Sort the list from closest to furthest
3. Cast out spokes at given intervals with a minimum length of whenever it collides with a wall and a maximum length of the given radius
4. Create and add to the ‘area list’ a polygon based on the previous spoke coordinate and the current spoke coordinate
5. Iterate list of visible wall nodes
6. Calculate new radius by subtracting the distance between the starting location and the node location from the given radius
7. Start over at the top of this list substituting ‘player’ for ‘node location’ and keep going until the new radius is too small

I really wanted to add (union) the polygons together to create one polygon consisting of the outer-most points. Unfortunately, that messes up and I’m left with what looks like a crumpled bridge at the best of times. For the time being I’ll have to use the list of hundreds (due to the recursion) of polygons as seen in the image above. It’s not so bad as in the game it’ll be displayed in between turns when the frames per second doesn’t matter. Perhaps there’s a Java package out there that could do the job for me, giving me a simplified list of the union of all the polygons.

A very minor update, barely worth mention.

You’ll notice the entire wall segment is enclosed in the radius around the ‘player’, that yellow circle at the center. The significance here is that the top-left point of the wall segment isn’t included in the list of accessible nodes! Why not? Because, the player can’t see that node (it’s on the other side of the wall segment). Another good thing in the image above, the yellow dot is flush with the two red nodes meaning it has the same x-axis as the node to its left and same y-axis as the node above.

It’s all theory, but I believe I’m close to achieving my goal. A little recursion to jump from one point to every other point in its line of sight, adding together all the places that the orange ‘light’ can shine on, and I should finally have my map of accessible areas. Remember, it’s the idea of having a string anchored to a location, and then mapping out only the locations that the tethered string can reach.

It’ll all become clearer when I get it working. You’ll see.

Trying hard to figure out an efficient way to do the following:

And so far, only coming up with something like this:

Imagine a thread of fixed length N stuck to a location on your desk. Now picture a coffee cup in the path of that thread. Now fill in only the area that the thread can reach.

I’ve tried to work it out on a whiteboard but that was only getting me so far with the subject. Now I’ve got a hunch that if I iterate (and recurse) the points within the line-of-sight from the closest to furthest points from the player that I can calculate the accessible region based on the player’s position, and how far the player can move (the length of the thread).

That brings me to Comparators. In PHP there’s a handy function called usort. It takes an array for the first argument, and the name of a function as the second argument. The function as a second argument is one usually written by you, the developer, to tell usort how to compare two elements in the array.

In Java you can accomplish usort via the Comparator interface which usually works out to something like the following:

int compare(a, b) {
	if (a == b) return 0;
	return (a < b) ? -1 : 1;
}

In this case I’d compare Point objects and sort them from closest to most distant locations from the player. For reference, this page was informative enough to show how to create and use your own Comparator.