Cellular Automata for Pathfinding in NetLogo

Last time we took a look at implementing a Cellular Automaton in NetLogo to do some simple image manipulation. We just scratched the surface. In class, the kids write pretty nice Photoshop Light applications.

Today we'll look at some more ambitious problem solving - using a Cellular Automaton to find a path through a maze.

Part 1 - finding possible paths

We'll use the image above as an example and a live model with all the code is at the end of this post.

Each square of the maze is a NetLogo patch. White square represent possible paths, Red is our entrance, green our exit. As we explore the maze, we'll color the cells yellow.

Remember, in a Cellular Automaton (CA), each cell makes a decision as to it's next state based on information about its neighbors (up, down, left, and right only in this case).

So, if every cell is looking around at it's neighbors, most cells don't have enough information. The only white cell that might be on the path from entrance to exit is the one next to the entrance - it might be on the path.

This leads us to the first step of our CA rule set:

(click images to enlarge)

Next time through, we notice that a cell might be on the path if it's white and it has either red or yellow neighbors.

Eventually, we end up with a yellow abutting green - the exit.

Notice that each yellow cell is also numbered. The number indicates how many steps it took to get there from the entrance. The implementation is trivial:

  • Start by giving each patch a variable step and starting it at 0.
  • When a cell is about to turn yellow, it should look at it's yellow or red neighbors, ask for their step value (they'll all be the same - think about why), and set it's step value to one more than that.

We'll use these step numbers to recover the actual shortest path.

Part 2 - recovering the shortest path.

We can now use the yellow patches with the step numbers to find our way back.

We're going to build a solution set.

  1. start with an empty solution set.
  2. take the only green cell not in the solution set (let's call it G).
  3. Ask G's yellow neighbor with lowest step number to turn itself green (that cell will be G next time around).
  4. Place G into the solution set (leaving the new green cell as the only green cell not in the solution set).
  5. Repeat 2 - 5 until we're back at the entrance.

This is one of my favorite intro topics. It's using a CA - something normally just presented as a toy idea, to solve a real problem. It reinforces parallel processing and foreshadows all sorts of pathfinding ideas to come.

Below is the complete NetLogo program. You can look at the code by clicking on the code tab at the bottom.

To run:

  • setup sets up all the variables and clears the world.
  • buildmaze builds a random maze.
  • solve is a toggle to run through an entire solution.
  • step single steps through the CA.
  • reset Resets all the variables and recolors the maze to unsolved.
  • The other buttons are toggles for drawing your own maze.

Cellular Automata, NetLogo and real problems

We've been using NetLogo in our intro course for years. It's a wonderful programming environment. Many of you recall the Logo programming language. NetLogo is like Logo but instead of programming a turtle, you write a program that's run by multiple, perhaps hundreds of turtles and also by the world the turtles live on.

Some of the reasons we like it are that it's:

  • An easy accessible textual programming language
  • Makes building a graphical interface trivial
  • great for modeling
  • Comes with tons of demo models

And now, with the latest version, NetLogo programs/models can be deployed as web sites. All you have to do is save your program as "NetLogo Web" and put it up on a observer somewhere.

If you haven't you should download and install NetLogo, run it, then go to the file menu and look at the built in models.

I also enjoy playing with Cellular Automata and NetLogo's a wonderful platform to play with. The turtles live on a grid of patches and just like the turtles, the patches will all run your program over and over.

The patches make perfect cells for a cellular automaton and you can implement a rule set in your patches.

NetLogo even comes with a bunch of built in demo models for Cellular Automata including Conway's Game of Life, probably the most famous CA.

On the other hand, Conway's Game of Life is somewhat cliche and while I find it fascinating, it doesn't really solve a practical problem, at least on on the surface.

So, I was looking for something more practical to do and something where we could explore some deeper CS concepts.

Image manipulation.

In class, we make a Cellular Automaton where each cell or patch is a pixel in an image. In NetLogo, you can do this with the "import-pcolors" command. Lower down, I have a demo that just manually colors patches - the web version of NetLogo doesn't yet support that command.

Task 1 - what if we want to shift the image over? The kids come up with a solution pretty quickly: "We can just have each patch ask its neighbor for its color." Here's the code they try:

To see what happens, scroll down to the NetLogo model below, click on setup and then hit the shift-naive button a few times.

It doesn't work.

What's going on?

It's a synchronization issue.

Suppose we have the following three cells in a row:


If cell 3 asks cell 2 it's color before cell 2 asks cell 1's color, we get the desired result:


But if cell 2 asks cell 1 for it's color first then cell 3 will actually get cell 1's color:


So now we have the students thinking about synchronization and parallel processing and they don't even know it.

The solution's pretty easy, break the problem up into two steps.

First, have every patch ask its neighbor for its color and then once everyone knows their neighbor's color, then change:

patches-own [next-color]

to shift-correct
  ; figure out my next color
  ask patches [ set next-color [pcolor] of patch-at -1 0 ]
  ; then switch to it
  ask patches [ set pcolor next-color]

You can run that by clicking setup again and then shift-correct a few times.

There's some of the beauty of NetLogo - we can get kids to think about some deep concepts while playing with an easy to use, fun, interactive environment with a real textual programming language.

Stay tuned for part 2 when I'll talk about creating a cellular automaton that can solve a maze.

Discussion Silos

In response to the past couple of days where my friends and fellow CS Ed advocates Alfred Thompson, Rob Underwood, and I had a nice little discussion via our blogs, Alfred wrote this.

It's great when a number of voices in the community have an open discussion but one of the things I found myself lamenting was the fact that a lot of the discussion isn't truly accessible.

Why not?

The silo known as Facebook.

I have no problem with Facebook - I like it and use it daily - it's a great way to keep in touch with former students turned friends. The problem is that much like Las Vegas, discussions that happen on Facebook stay on Facebook.

Recently I've seen a number of blog posts, some mine, some Alfred's, some others where the post garnered nary a comment. Head over to Facebook and if you're friends with the right people, you might find a lively, informative discussion.

In one case in particular, one post had independent, overlapping discussions in at least three Facebook threads.

How much richer would the discussion have been in a public forum plus it would be left open for people to discover in the future.

Personally, I use Disqus. I like it since I can also follow people on it and I can just embed the code in any page but others like what Wordpress or Blogger uses for comment threads. In any event, it keeps the conversation open.

Is this really a problem? Maybe not but I do wish people would look beyond Facebook for discussions.

It's something I've been trying to get my students to do for years. I've used a number of tools for class communication:

  • mail lists
  • Piazza
  • custom forum software like vanilla
  • slack

and haven't found anything that really does the job quite right. I'm still looking.

The kids use these but invariably end up also setting up a Facebook group for my class and their other classes. I encourage this - they certainly should have a forum that I can't see. How else can they plan that surprise party for me :-). In all seriousness though, ideally they should have a forum free of teachers but they should use the one with the teacher as much as possible.

The real problem with the kids setting up Facebook groups every year is that there's no institutional memory. I see the kids, year after year, have to clear the same hurdles. If they started thinking outside of the silo of their Facebook communities and just had an ongoing community for each class - one that passed on from year to year, it would be of tremendous value for them.

So, I'd like to encourage everyone out there to get our discussions out into public forums. It would be terrific if more of us would blog or blog more often and also to take the time to add to the dialog in a public place.

Teaching Coding - getting beyond superficial syntax

The other day, Alfred Thompson put up a piece about coding in multiple languages. Alfred references a post written last May by Rob Underwood.

Both pieces are worth a look.

Rob is trying to illustrate many of the superficial similarities in popular languages.

In the comments on Alfred's blog, both Alfred and I alluded to coding in an appropriate style for the language.

For me the issue is even bigger.

Learning to code is all the rage and places to learn are popping out of the woodwork.

There are:

  • In classes, in schools, with teachers
  • Drop in programs in schools.
  • Programs run by coding schools
  • Moocs and other online resources
  • Summer and weekend programs

And probably more. All of these options are giving more and more people a way to learn to code.

That's great, but it also raises concerns given that very few people involved in CS education have both strong teaching and CS backgrounds.

What I'm starting to see are the results as I meet young people coming out of all of these programs.

Unfortunately, what I'm frequently seeing, at best, is very superficial coverage of syntax.

I've seen kids who would have no basis for understanding that the ramifications of this Python code:

a = 30
def f():
  print a

print a

and this Javascript code:

a = 30;
function f(){
  a = 20  

are very different.

It gets worse when I meet kids who "know C" because they were exposed to constructs like:

for (i=0;i<10;i++){
 // code goes here

I think the most common issue come from kids being "taught" programming using javascript which seems deceptively simple but is really rather deep.

It's important that as CS becomes more mainstream that we make sure that we have teachers and programs that are teaching the real deal. It can be fun and accessible but it does require teachers that know their stuff and are willing to continue to learn.

Do our kids deserve any less?

Leaving Stuyvesant

Almost twenty six years. That's how long I've been a NYC public school teacher. Most of that time at my alma mater, Stuyvesant.

A couple of years ago, the school paper wrote up an overview of my career. I re-posted it here. I'm somtimes amazed at where we are now and how we got here.

Regulars here also know my frustrations. To Stuy, I'm an interchangeable, generic math teacher and the DOE has shown no interested in supporting what we've built. I've also written about my concerns with the direction the city's going with respect to K12 CS education.

It was time for me to start the next phase of my career.

I'm happy to say that I will be joining Hunter College in late January. I'll be developing their CS Teacher Ed program and also working with their computer science undergrads. I'll also have the opportunity to work with the Manhattan/Hunter Science High School and Hunter College High School.

I also look forward to the opportunity to work more closely with my friends in the K12 Ed space.

I'm very excited about this opportunity but it feels a bit weird after being in the same place for so long. I don't feel any special attachment to the institution that is Stuyvesant, my allegiance is to my current and former students and that community isn't going anywhere. Next year I'll still be working with terrific young people, just in a different location under a different name.

I will miss the team that we've put together but even then, we get to continue our work with CSTUY.

With the new year comes new opportunity and I can't wait.

Advent of Code - because I'm an idiot


I wish our kids believed us when we tell them that we have the same programming troubles as they do. We stare at code for hours not seeing problems that could be a simple as passing the wrong value. We spend an inordinate amount of time trying to see the problem and then realize that we just forgot something silly.

At this point, it's common for us CS teachers to tell each other "I figured out the problem I was having – it's that I was an idiot."

Last time, I talked about Advent of Code and how I was somewhat behind the curve. In part because I started late and in part because I've been using it as an excuse to learn some Clojure.

Here's how I burned over two days on Day 6.

The problem is pretty straight forward. You have a 1,000 x 1,000 grid representing a light board and you have to repeatedly do operations on smaller rectangles on that grid. Turning individual lights on and off, if you would.

If I were doing this in a language like C, I'd probably just take a big block of memory and loop through the instructions but since I was working in Clojure, I thought I'd try to do something in more of the functional mode, that is, with immutable data types.

After a while, I was getting the feeling that it was going to be too slow so I shifted to just modifying a big block of memory.

Try as I could, I couldn't get it to work. I was sure my algorithm was fine - it wasn't a hard problem, but I couldn't get the right answer.

After a while, I started looking at existing solutions and they were basically the same as mine.

I was stumped.

Two days after the start, I figured it out.

No matter how hard you try, if your problem specifies the data in the form row1,col1 row2,col2, you're not going to get the right answer if you decide that the input is in the form row1,row2 col1,col2.


Ok, after that the problem was pretty trivial.

Hopefully I'll have some time to do problem 7 and beyond this weekend.

If there are any Clojure people out there, I'm putting my solutions up on GitHub - I'd love some feedback on how to get more idiomatic.

Advent of Code


Has everyone seen Advent of Code?

It's a site with a series of programming problems that are being revealed one a day, a la an advent calendar. You can read more about it here.

I came to the party a little late so I'm only up to day 6.

Each problem comes in two parts. The second is revealed after you complete the first. Both students and teachers are enjoying the problems.

What I like about the Advent of code, besides the one a day release, is the fact that at least so far, the problems aren't super crazy hard. They require a little thought but they seem very doable.

For me, that makes them a perfect platform on which to play with a new language. I'm working through these in Clojure. I've been putting my solutions up here. I have no idea if my code is "good" Clojure but it's been fun nonetheless.

So, if you're looking for a nice set of small programming problems and want to explore something new, check it out.

We're Number One!! We're Number One!!!

I woke up this morning to an email from my principal "Stuy is #1." This followed a bunch of Facebook posts by friends and alums of a similar vein.

It was all about a couple of reports, here, and here. It turns out Stuy is ranked #1. Woo Hoo. We're awesome.

Of course, everyone whooping it up now was quick to say "all those rankings are meaningless" back when US News and World report ranked Stuy way down on their list.

We all know what makes a great school: great students. At least in terms of perception. Look at most of these lists and they'll be dominated by high schools that take in high performing students.

Truth be told, in many ways, Stuyvesant isn't a special place, but more on that down below.

In terms of the ratings and rankings they're meaningless but in a way dangerous. I see it at Stuy. Under the current administration AP is the word of the day. It's all Advanced Placement all the time. Why? That's one of the ways to rise up in the rankings. So are the school surveys which is why there's been more pressure to get those done.

My feelings? AP is all about making money for the College Board. I'm not a fan of "early college," I'm a fan of enrichment. I've said it many times - if a course is such that it can be mastered equally well by a 15 year old in 10th grade as by a 19 or 20 year old in college, well, it really isn't college level. High achieving, well prepared high school kids can do college level work in 11th and 12th grades but probably not in all subject areas. Sure they can memorize, ape, and mimic, but the depth of knowledge won't be there. Regardless, we should trust schools and teachers to do it right. Schools can roll out rigorous courses as good or better than AP. There's no real need for the College Board seal of approval. Look at Fieldston and other private schools as examples.

We've been teaching our own introductory CS class at Stuy for years. The entire team knows that it's far superior, at least for our students, than the new AP CS Principles course yet our principal keeps pushing the AP course.

I've spoken to a number of administrators from highly regarded schools over the past couple of years and all are pushing test scores, AP classes, and anything to get those rankings up.

So, there's a movement to make Stuy a generic school that happens to have high performing students which brings me back to are we number one or indeed are we special?

It certainly has a couple of things going for it. Great kids and a large size. The large size ensures lots of electives. Stuy is one of the few schools with a robust set of humanities classes, stem classes, multiple music groups, and more. That's important. When I sent my kids to Stuy a big part of the decision was due to the fact that they'd be surrounded by smart kids whose interests range all over the place. The kids come from all backgrounds. Also, my kids would be able to explore all of their current interests and maybe even pick up some new ones.

But then there's the other side. We have lots of electives and some are great but then, some are lousy. Just like any other school we have some amazing teachers and some garbage. For the most part, if you switched Stuy's faculty and administration with another school, you might lose a few special electives and gain a few different ones but by and large people wouldn't notice the difference.

Regardless, Stuy and all similar institution should be charged with something extra. We should be leaders in developing programs and sharing them with other schools. We should be developing experiences for our kids that are appropriate to their level of development, not being happy with high regents scores or the fact that we had a bunch of Intel semifinalists, many who probably would have accomplished similar feats regardless of the school they attended.

Kowtowing to the rankings kills that possibility. To reach the top of the charts you have to follow the book. If you want to lead, you have to write the book.

It would be silly of me to judge my success by how many kids pass the APCS exam. It's an easy test for them. I've worked hard not to create classes because I like them, but because they make sense for our kids. They sequence appropriately, and they give the kids opportunities and experiences that they wouldn't get had they not attended Stuy.

Unfortunately, since the late 90's I haven't had the luxury of a supportive administration that shared my vision. As the school and the system moves more towards the rankings you're going to see educational leaders more and more marginalized and finally eliminated.

So, is Stuy number one and is it special? As long as it's given the same type of kids it's had for the past 100 or so years, the kids will do fine. Is it really special? Well, unless it starts really think about what the kids need and deserve, maybe not so much.

Other People's Code

The coding on their project is reminiscent in many ways of an Ed Sheerhan song. It left me in tears and very confused as to what the author was trying to accomplish.

– a student commenting on their most recent project.

We had some fun last week. Well, OK, I had some fun. The SoftDev classes had just finished a little project. Basically, a blogging platform. Something that would tie together all the tools we've been using. Flask, user management, an SQL database (SQLite), and a nice looking front end.

It was also the first real group project so the teams have started to learn how to work together.

After some project demos, it was time for part two: NOSQL. We explored MongoDB and then it was time for the project - clean up the previous project through the use of techniques like template inheritance and convert the database backend to MongoDB.

The catch? Each group would take another groups project and use that as their starter code. The rules? They could modify and refactor but they couldn't rewrite.

It threw the groups for a loop but I ultimately think they had fun with this.

Afterwards each group gave a write up to their starter group. What made their life easier, what made it harder. We then circled up for discussion as a class.

It was terrific.

First, it was great that we've gotten to a point where everyone feels comfortable giving each other constructive criticism. We've gotten to the point where the class is a team.

Beyond that, I'm hoping that everyone got a lot out of the exercise.

As each group talked, common themes arose:

  • consistent commenting is good
  • variable names matter
  • unused code and files can be misleading
  • overall code structure, file names, and locations are important.
  • and much more

We're now going to start a discussion of coding style, standards, and documentation.

I've got to say that I'm very happy how this little experiment worked out.

Enter your email address:

Delivered by FeedBurner

Google Analytics Alternative