Posts Tagged ‘algorithms’

.

Deciding where to go

by Brad

As part of an experiment I was working on, I needed to decide how an object should turn based on what it saw. Some objects would attract it, and some it would prefer to turn away from.
Turns out that’s more complicated than I expected.
So I pulled that portion out to test in an interactive example.

I’m not dissatisfied with the result, but it remains to be seen how it will work out in the larger experiment. For example, the algorithm seems overly complex. There are a whole bunch of Math.sin, Math.cos, and Math.atan2 calls. I don’t know how slow or fast these really are (I should check), but I wonder how it will fare as the number of objects increases. It’s possible that I tend to worry about that sort of thing too much: future cost.

(Either JavaScript is not active or you are using an old version of Adobe Flash Player. Please install the newest Flash Player.)

Click to set pleasing items, and ctrl+click to set displeasing ones. You can drag them around, but the longer your mouse is down the larger they will grow, and with it their effect on the blue circle.
Press the space bar to clear them.

(more…)

Shaun said i should describe the algorithm but im scared

So you have these two shapes, right? One of them is the guy who can see, and the other a bitter enemy who blocks his line of sight.
Stretched between their centres, where their souls live, is an imaginary line:

001

The red blob is our protagonist, and the blue hexapod an enemy of his sight.
Perpendicular to that line, is another imaginary line:

002

For each point of the hexepod, we want to find where it falls on that line. Or, to calculate the distance from the point to another point on the original line. Also the line made by those two points should be perpendicular to that original line:

003

The point at the greatest distance, on each side of the line, is the point we will use when drawing the occlusion shadow. Here, Karl pointed out a problem: Our algorithm assumes parallel vision lines, and so the approach will break down as a shape nears a source, especially if that shape is much larger and irregularly shaped. In many cases, this shouldn’t pose too much of a problem. Well. In some cases. In the case blogged earlier, at least.

004

The min and max points are the ones we use to calculate the blocked area. We can draw the lines from the centre of the guy to the points in question, and all we have to do now is extend those lines from the points until they are off the screen:

005

That is all. Also there are probably some neat optimizations we could implement, especially if the world is based on tiles. Any objects contained within tiles in darkness could easily be excluded from calculations – which would work even better if we first sorted the list of objects by proximity to the character. We could discard any points that lie on tiles which couldn’t possibly hold the most distal points. And if we have control over objects, we could return only points that could possibly block sight.

Your friend,
Brad

.
.