Category: Tech

How Far Can You See In The Woods (part 2)

March 14, 2015

If you’ve been reading the comments of the previous blog post, you will have seen Bernard coded the simulation I described. You can play with it here. This simulation doesn’t answer the original ‘field problem’, but instead the more general problem of ‘can you see your friend if you’re both standing in a forest’?

{A quick note: if it appears to crash your browser, just force-quit because the code is in an infinite loop. This happens a lot with high wood density and low tree radius. On an ipad, force-quit by returning to the home screen then double tapping the home button and swiping the browser up to close it.}

I’ve done some analysis using this early version of the simulation, and here’s a table of results:

That’s a surface plot of the percent chance to see your friend indexed by wood density (0.1 = 10% trees) and tree radius. A few comments:

– The distance between you and your friend is randomized.
– The tree position is randomized.
– The tree radii are unphysical, and the code doesn’t seem to support non-integer (cm) values.- I used 2500 trials each, except when radius was low (percentage ~ 0) where I dropped to 250.

Interestingly you can see the percent chance increases with tree size, but decreases with wood density. You are more likely to be able to see your friend if the trees are large, and less likely if they are close together. Currently there is no upper-bound on tree size, and it seems the percent chance simply increases as they get bigger and bigger.

As for the distance question, I’m happy to report that Bernard also added metrics to help you calculate this. I’m going to pick 20% wood density and 7m tree radius (!!) as an example. Here’s a simple representational plot of one such forest complete with friends:

In the above – generated by the simulation – the friends are far apart and can’t see each other. The obvious question is what is the relationship between distance and ability to see each other, and here are the metric results from 1000 trials with these parameters:

We can’t read too much into these since position is randomly chosen, but on first glance it seems (in this case) the friends were more likely to see each other at about 50 meters. However if you look at the bottom plot, you’ll notice there were quite a few occasions around the 50m mark where they could not see each other. I’d estimate about 20 or so, which means only about a 60% chance (seen/total) of seeing each other at about 50m. Glancing at the two plots it is, as we’d expect, the case that the chance to see each other decreases with any distance beyond standing adjacent.

So the results are interesting, but these are early days yet. Were I to modify the current code, here’s what I would do:
– Input wood density input as an integer between 1 and 99
– Input tree radius in cm
– Output result plots as percent chances per distance – one plot, rather than two, of (times seen at that distance)/(total times separated by that distance)
– Add variable tree radii
– Add foliage transmission support- Make the map circular, and distribute the trees according to a Gaussian distribution (this is more physical) {This may be for V2.0}

If and when these adjustments are made, you may see part 3 of this post 🙂
–

How Far Can You See In The Woods?

March 12, 2015

This is one I’ve been thinking about for a while: how far can you see in a forest?

I’ve always been intrigued by the effect forests have on our vision. Even in forests where trees are far apart that you can’t touch two at a time, you usually can’t see too far. When Bernard and I went up to the Grand Canyon last year, the forests there are very light on underbrush and the trees have a decent distance between them and you still can’t see much further than a few dozen feet. When I was camping in January and I got up early and saw pademelons everywhere, I couldn’t see them beyond a few meters into the woods.

So I’ve been thinking, is there an equation that governs view distance in a forest? Which naturally led me to try and devise one myself.

Once you sit down and think about it, you find it’s a bit of an open-ended problem. So I decided to start by thinking about an easier problem, and then expanding from there. So consider this one:

“You stand somewhere on one side of a flat field, and your friend stands somewhere on the other side. The field is full of trees. What is the percent chance you can see your friend?“

This is not a brain teaser with an easy answer, and the result will depend on many things:
– Where you stand
– Where your friend stands
– The size of the field
– The number of trees
– The size of the tree trunks

Problems with many unknowns can get difficult to solve quickly, so the first step is to eliminate some. The first two (location of you and your friend) can be expressed as the distance between you and them. The last three (field size, tree count and tree size) can be expressed as a ‘wood density’ (ie. the total cross-sectional area of the trees divided by the area of the field).

I speculate the general solution is some function of the distance between you and them, and the wood density. But how does one calculate the result?

As I teach my students, always approach a problem from extremes. The two extremes here are easy:
– If the wood density is zero (there are no trees) the chance you can see your friend is 100%
– If the wood density is 100 (the field is chock-a-block with trees) the chance you can see your friend is 0%

So we expect an answer somewhere between 0 and 100%. This may seem trivial, but there are problems in which the percent range can be much tighter and it’s useful to know we have the full 100%.

But what if there is only one tree? Consider these possibilities:

On the left you (A) can’t see your friend (B) because a tree is smack in the middle. In the middle you can (the tree doesn’t block your view), but on the right you can’t either because the tree just blocks your view. Any general solution must account for all such possibilities (and an infinite amount more).

So how to calculate a percent chance for one tree? There is no way I can surmise to solve this via a general equation solution, so the required tool is computer simulation, specifically Monte Carlo simulation. In essence: generate a very large amount of ‘maps’ (of you, your friend and one tree) and calculate the percent chance from solving each and adding them.

For instance, if the only possible configurations were those shown above, the chance of seeing your friend would be 33.3% (only one in three maps). Of course there are many, many maps though (as many as you want actually), and it would be impossible to solve them all, so a more rigorous method is needed.

Here’s how I would do it – and I welcome any theorists to give their techniques in the comments. This is (at this point), for one tree only:

1) Randomly generate your position (A) on the edge of the field
2) Randomly generate the position of your friend (B)
3) Determine the vector connecting the two of you (AB)
4) Randomly determine the position of the tree
5) Determine if the vector between A and B is blocked by the tree

This last step is trickier than it sounds, and the easiest way to do it (aside from a clever technique I discuss below*) might be to:
5a) Calculate the vector passing through the center of the tree perpendicular to the vector AB (this just requires some vector algebra)
5b) Calculate the intersection of these two vectors (more vector algebra)
5c) Calculate the distance between the point of intersection and the center of the tree (easy)
5d) If this distance is less than the tree radius, line-of-sight is blocked

The simulation would repeat the above steps many (n) times, incrementing a counter (p) by 1 every time you could see your friend. The final result would simply be (p/n)*100%

I imagine with only one tree the percent chance would be very high. But what about many trees?

That’s only 3 possible examples (from a pool of infinity) of five trees (well, six on the left!). You can see how much more complex the problem seems to become.

Interesting though, the simulation wouldn’t change much. The only difference would be to step 4 above, which would become:
4) Randomly populate the field with trees, saving their positions in an array

And then step 5 would be repeated for every tree. You wouldn’t have to test every single tree against line-of-sight for each AB vector, you could just stop when one blocked the view.

With this modified algorithm, I’d save (into my output file) the following:
1) Position of you (A)
2) Position of friend (B)
3) Size of field
4) # of trees
5) % chance of seeing friend (output of simulation)

Tests would have to be run to find out how many times the simulation needed to be ran. One thing I learned writing my simulation for my PhD was how few runs were actually necessary. My code would have happily ran all day long simulating billions of photos (each of which required hundreds of calculations) but in the end I stopped at only 1000. I found that the variability of the results for photon counts above 1000 was essentially 0, so there was no need to run more. It would be interesting to do the above coding and plot the results vs ‘maps’ ran and see where the plot gets flat. I bet it’s lower than we’d expect.

Once the basic simulation was in place, modifications I would add include:
– Variable tree size. The wood density would decide the total cross-sectional area of trees, and you could rather easily vary the radius per tree and keep track of total area so as not to exceed the desired density
– Foliage. Trees (bushes) could have a ‘transmission ratio’, possibly linked to a secondary radius (to discriminate between trunk and leaves). So line of sight could be half-blocked for instance if you were viewing your friend through leaves (as opposed to blocked by a trunk)
– Variable field size. The field is nothing more than a construct to give some constraint to the problem. It would be trivial to instead solve the following: “You and your friend stand in a forest full of trees. What is the percent chance you can see your friend?“

I strongly suspect the results would show a strong proportionality between the magnitude of AB, the wood density and the chance of seeing your friend, and it’s likely an equation could be fitted to allow for a general solution. It’s tempting to suppose the trivial result would simply equal wood density (ie 50% trees = 50% chance), but my gut tells me it isn’t that simple.

One interesting consideration is the dimension of the field, and how it may affect results. I have mostly ignored it here, but it may be worth considering. Consider the following examples:

Each permutation has 6 trees, but the first two have very narrow fields, both of which will lead to very low chances to see your friend (for random A, B positions). It’s true that the ‘wood density’ varies strongly between the first two the one on the right, and I wonder if that will be enough to correlate the results. In other words, can the exact field dimensions actually be ignored?

So lets return to the general problem, and what has caused me to think about all this: How far can you see in the woods?

It’s a much more interesting problem to imagine, but I think I may save it for another post 🙂

About that clever technique: It occurs to me a completely different way of solving this would be to do it graphically and exploit hardware graphics techniques. For instance, make the trees sprites and draw a vector between A and B and see if there is a collision with a tree. Do this enough times and save the results. The resolution (and I don’t mean computer screen resolution) would be necessarilly less, but maybe this technique – which saves a lot of coding and vector algrebra calculations – could work?

2014 in Games

December 20, 2014

During 2014, my game collection saw its smallest growth in 17 years, but I ended up spending more in total than I had in the last 4 years. How was this possible?

That’s the answer: I went into 2014 without a Vita (PSV), and will leave the year with a Vita and 20 games for it. This isn’t to say I adore the system (it has many flaws…), but it does have many of the sorts of games I like to play and since I believe the system is dead, I rushed to buy them all this year before they became difficult to find.

In total I bought 46 games in 2014 and spend a total of $1613.90. That’s an average cost of $35, which is a big increase over previous years. This is because I bought zero iOS games this year, and instead concentrated on 3DS and PSV software.

Here’s the charts:

That’s the breakdown of units sold per system, with the Vita at 20 and the DS at 1. Despite being owned for longer than the Vita, at only 5 games purchased the Wii U isn’t seeing much use…

That’s the dollars spend breakdown, and you can see the Vita ate the lion’s share of my spending. The tiny sliver for the DS is because the only game I bought cost $5 🙂

As for the games themselves, and my playing habits, looking back on 2014 I would have to say it was a mixed bag. The entire first half of the year (and into summer) was a bit of a drought, with me not playing much at all. In particularly I barely ever turned on the consoles (PS3 and Wii U) during those days.

But then something clicked after my summer vacations and I found myself become re-interested in gaming as the year moved into the fall. In particularly I very much enjoyed some Vita games like Toukiden and Demon Gaze and by mid fall the 3DS had me entirely under it’s spell with two masterpieces (see below).

BeforeI get to my favourites, two games deserve a special mention…

The first is Super Smash Bros for 3DS. This year Nintendo released Smash Bros on both 3DS and Wii U. I purchased the 3DS version, and will eventually get the Wii U version as well. The 3DS version however was, in my opinion, a bit of a square peg in a round hole. While Nintendo did an admirable job of stuffing a massive amount of content in, the game suffered from poor controls and a design not ideal for such a small screen and I put it aside quickly, with the intent of saving myself for the Wii U version.

The other game is Puzzle & Dragons, last year’s game of the year winner. Yes I’m still playing it (>580 days played now), yes I’m still loving it and yes I still think you should play it too. But I won’t include it in favourite lists this year since it disqualifies having won last year!

So my favourite games of 2014, in reverse order:

3) Hyrule Warriors (Wii U)

This one came out of nowhere! Koei stuffed Zelda into the Dynasty Warriors engine and produced a game almost better than both! If you like hack-and-slash games then this one is for you, and the astonishing amount of content could take hundreds upon hundreds of hours to beat. Bravo Nintendo!

2) Theatrhythym Final Fantasy: Curtain Call (3DS)

Curtain Call took everything that was good about the first game, multiplied by ten, and produced maybe the best sequel ever. I played this like a demon, leveling every character to maximum (sometimes more), SSS ranking every song and collecting all the cards. This is a music game ever that can stand along side Ouenden, and took over my life for a month or so earlier this year. While I was playing this I would have said it was a no-brainer for game of the year, but then something else came out…

1) Fantasy Life (3DS)

Level 5 have created an action RPG with near perfect controls, beautiful graphics, and vast amounts of stuff to see and do. In addition to the usual systems (fighting monsters, casting spells, talking to NPCs etc) the game includes twelve classes (from Paladin to Cook) and you can go fishing, brew potions, make (hundreds and hundreds) of items, armor and weapons and recruit followers. It starts off easy and a little confined, but after a dozen or so hours of play you realize how mind-bogglingly big it is and how much time you’d need to max everything. Which I did. Including all the expansion ($9 on the 3DS store) content! All told I played for about 150 hours before putting it aside, but I suspect one day I’ll return just to finish off the (very difficult!) ‘Master Quests’. This isn’t just the best game I played this year – this is one of the best games I have ever played. Highly recommended.

As I always do I’ll end with a question: how was your year in games? What were your favourites in 2014?

Robot Claw