Calculating the Neighbors For Every Picnic Spot

We're going to be finding an optimal placement of our picnickers using simulated annealing. This means, all the picnickers are going to "run around" like crazy on the picnic map and when they find people they like, they're going to move slower and "crystalize"... It will be as if the picnickers are molecules in a beaker that are slowly forming a crystal.

In the process of simulating this, we'll need to know what the neighboring spots are for every picnic spot on the map- We'll need to know for two reasons: First, once we start putting people in the spots, we'll need a way to tell how well they'll like their neighbors to make them slow down to crystalize. Second, while all the picnickers are randomly "bouncing around" in the park, we need to know what spots the can "bounce into" next. Here is some code that calculates neighbors:

  
  let shortestLinks :: Int -> [Link] -> [Link] 
      shortestLinks n = (take n).(sortBy $ comparing linkLength) 
       where linkLength [a,b] = distance a b 

  let sittingNeighbors :: Int -> [Point] -> [Link] 
      sittingNeighbors n p = nub $ shortestLinks (n * (length p)) [[a,b] | a <- p, b <- p, a /= b]

  let sitting = sittingNeighbors 4 centers

  writeFile "tut6.svg" $ writePolygons $ (green park) ++ spots ++ (red sitting)

Here's what the resulting tut6.svg file will look like:



The way neighbors are determined is to simply check every possible picnic spot pair, sort them, and select the shortest. Naturally, this means that centrally-located spots will have more neighbors (and would probably fetch top dollar, if it wasn't for this $#&@! real estate market right now...) while the edge spots will have less- Which actually nicely handles the cases of outliers in the picnicmob questionaire... If you end up in a corner of the park on picnicmob.org you're probably some kind of weirdo. ...Uhm... Wait... I mean... it's probably just coincidence, really- forget I said that...







What's good about this code?

If you look at the sittingNeighbors function (which builds all possible spot pairs and sorts 'em) you see something in square brackets [ ]... This is a neat feature in Haskell called a list comprehension... In this example, it reads as "For the cartesian products of all spots, represented as spots a and b, where those spots are not identical, return a the list of a-b pairs". Since lists are so central to Haskell, being able to write stuff that generates lists in this fashion allows some algorithms to be expressed very clearly and succinctly.



What's Bad About This Code?

Somewhere, deep in the brain of every programmer, is a neuron that has only one role in life: Whenever a sound is recorded by the hair cells of the ear that sounds like "Cartesian Product", this neuron will dump unimaginable quantities of neurotransmitters at the nodes of other neurons, that translate into the neuron-equivalent of "Oh my God!! INEFFICIENCY ALARM RED!! All Neurons to full alert! RUN RUN RUN!!!" Enough said.

Another problem, looking at the resulting map, is that this sittingNeighbors function is prone to lead to "islands"... this is fine if when we're measuring happiness with neighbors when people are sitting (since people on other sides of walkways aren't really that good for conversation, anyway...) but is lousy for letting our molecule-people bounce around- They'll never walk/bounce into the islands... Which is why we need to define another function for neighbors... you can probably guess what it'll be called...

NEXT