Since I can't comment on my own blog, here we go. And people on blogger groups don't know either.
I was reading that some of the tree methods were mainly used for static collision culling, due to their expensive insertion and deletion properties. I don't know yet if Quadtrees have the desirable properties.
Thanks for the link on the Voronoi paper. I'll take a look at it.
@Wally thanks. I'll see what I can do.
@Hal Oddly enough I saw your simulation on youtube when I was browsing around the other day. Do you have source I can look at for that?
Friday, February 13, 2009
Thursday, February 12, 2009
Introducing Frock, a flocking chicken simulation written in Lua with Löve
I recently learned about LÖVE, a 2D game framework for Lua off HN. It looked simple enough, and when I ran the particle system demo and it was pretty fast. It seemed faster than what Ruby Shoes would be able to do. I got rather excited because
I've been fascinated with decentralized systems since right after college--one of them being flocks. But how do they work? For a long time, ornithologist (bird scientists) had no clue how birds flocked. Birds seem to be able to move in unison, as a super-organism, swooping, expanding/contracting, splitting. When you see massive waves of these things (these are starlings), it's something to behold. Who is the leader? How do they coordinate these flocks?
We still don't exactly know, since we don't yet have the capabilities to tap into a bird's decision making mechanism in real time. However, in the 1990's, Craig Reynolds demonstrated that you can get very convincing flock-like behavior generated procedurally, using three simple rules. And it ends up that you don't need a leader to get flocking behavior. All interactions can be local, and each flock member (or boid, as he called it), just needed to follow three simple rules:
So here it is. Introducing Frock, a flocking simulator in Lua Love.
I release it now, because while it's primitive, it works (release early, release often!). The screenshot doesn't really show it well, they fly about in a flock, hunting for plants to eat. It's rather mesmerizing, and I find I just stare at it, the same way I stare at fish tanks.
It was originally a port of the Ruby Shoe's hungry boids, but I used flying chickens lifted from Harvest Moon instead. I originally had cows flying about, but without flapping, it just wasn't the same. I also made the repulsion vector increase as a function of decreasing distance. Otherwise, the chickens didn't mind being right on top of each other if they were on the inside of the flock.
My immediate goal is to make it support more chickens, so I can get a whole swarm of them. Right now, I'm using an inefficient algorithm to calculate which chickens are neighbors (basically n^2 comparisons). So if any of you have good culling techniques applicable here, I'd love to hear it. I'm currently looking at R-trees.
There are different possibilities as to where it could go. I think while lots of people have written boid simulations, they haven't taken it much further than that. While I've seen ones with predators, I haven't seen anything where people try to evolve the flock parameters, or try to scale it up to a large number of chickens. One can also do experiments on whether different flock parameters have different coverage of the field, or which set of parameters minimizes the time a plant is alive.
If at the basic, it becomes a framework for me to write 'me and my neighbors' decentralized algorithms, that'd be useful too. And since Lua is suppose to be embeddable into other languages, that makes it an even more exciting possibility. Later on, I'll write a little something about Lua.
Well, if you decide to try it out yourself, get to the Frock github repo, and follow the readme. Patches are welcome, but note I haven't decided on a license yet--but it will be open source. If you have questions, feel free to contact me or comment. Have fun!
- I've always wanted to make my own game. A lawnmowing game comes to mind.
- I wanted to see if I could create a large flocking simulation
I've been fascinated with decentralized systems since right after college--one of them being flocks. But how do they work? For a long time, ornithologist (bird scientists) had no clue how birds flocked. Birds seem to be able to move in unison, as a super-organism, swooping, expanding/contracting, splitting. When you see massive waves of these things (these are starlings), it's something to behold. Who is the leader? How do they coordinate these flocks?
We still don't exactly know, since we don't yet have the capabilities to tap into a bird's decision making mechanism in real time. However, in the 1990's, Craig Reynolds demonstrated that you can get very convincing flock-like behavior generated procedurally, using three simple rules. And it ends up that you don't need a leader to get flocking behavior. All interactions can be local, and each flock member (or boid, as he called it), just needed to follow three simple rules:
- Attraction: Move towards the perceived center of the flock according to your neighbors
- Repulsion: Avoid colliding with your neighbors
- Alignment: Move in the same direction and speed (velocity) as your neighbors.
So here it is. Introducing Frock, a flocking simulator in Lua Love.
I release it now, because while it's primitive, it works (release early, release often!). The screenshot doesn't really show it well, they fly about in a flock, hunting for plants to eat. It's rather mesmerizing, and I find I just stare at it, the same way I stare at fish tanks.
It was originally a port of the Ruby Shoe's hungry boids, but I used flying chickens lifted from Harvest Moon instead. I originally had cows flying about, but without flapping, it just wasn't the same. I also made the repulsion vector increase as a function of decreasing distance. Otherwise, the chickens didn't mind being right on top of each other if they were on the inside of the flock.
My immediate goal is to make it support more chickens, so I can get a whole swarm of them. Right now, I'm using an inefficient algorithm to calculate which chickens are neighbors (basically n^2 comparisons). So if any of you have good culling techniques applicable here, I'd love to hear it. I'm currently looking at R-trees.
There are different possibilities as to where it could go. I think while lots of people have written boid simulations, they haven't taken it much further than that. While I've seen ones with predators, I haven't seen anything where people try to evolve the flock parameters, or try to scale it up to a large number of chickens. One can also do experiments on whether different flock parameters have different coverage of the field, or which set of parameters minimizes the time a plant is alive.
If at the basic, it becomes a framework for me to write 'me and my neighbors' decentralized algorithms, that'd be useful too. And since Lua is suppose to be embeddable into other languages, that makes it an even more exciting possibility. Later on, I'll write a little something about Lua.
Well, if you decide to try it out yourself, get to the Frock github repo, and follow the readme. Patches are welcome, but note I haven't decided on a license yet--but it will be open source. If you have questions, feel free to contact me or comment. Have fun!
Tuesday, February 03, 2009
Can't comment
Somehow, blogger doesn't let me comment. I'm not sure why, and I'll fix it some time later, or export to Posterous.
Thanks trevor. I've subscribed to your weekly digest. I've been reading Hacker News all this time. However, it wasn't so much that I didn't have time to read, as I didn't have time to synthesize them.
And oh, thanks for the Perforce slides. They've been really helpful.
Thanks trevor. I've subscribed to your weekly digest. I've been reading Hacker News all this time. However, it wasn't so much that I didn't have time to read, as I didn't have time to synthesize them.
And oh, thanks for the Perforce slides. They've been really helpful.
Nerd time, issue 15
Nerd time is back, due to some complaints in person about how they missed it. In brief, nerd time is an occasional mailing list I send out to people I know that work at research labs. They're usually slow in getting the tech world news, so I thought it would be fun to pass along some tech news bits. This is issue 15.
-----
Hi all.
Well, after starting work at Frogmetrics last May, I got really busy writing code, learning about business and startup related things, and absorbing sales and marketing stuff, that I simply read a lot less. There was also less tech news going on that I felt was significant. When there's no significant news, the echoes become pretty loud in the echo chamber. Since I didn't hear anyone say anything about it, I figured no one read nerd time. And since I was reading less, I became more intellectually lazy. Hence the 10 month silence on nerd time.
But about a month and a half ago, I got in-person complaints that nerd time was no longer being sent out, so here it is reinstated. Some of these might be old news, but it's what I collected and found was significant over the last couple of months. And what the hell, old news in the tech world takes a while to get to the research lab world, so hey, this might be new to you. This time is mostly about source control and languages. I have other things I'm playing with that might be of interest, but will reveal them as I mature them.
Git the decentralized version control
Decentralized version control isn't anything new, but its adoption is. Git is pretty powerful. I don't go into all the reasons why. You can read about it in my post here. But on a deeper level, git is essentially a versioned filesystem. In fact, what's most interesting about it is how general it is and how you can use it for things other than version control. You can use it to synchronize address books, remote deploy code, or even as a basic wiki or blog.
http://git-scm.com/
http://whygitisbetterthanx.com/
http://eagain.net/articles/git-for-computer-scientists/
Github a social network for developers
Github is like sourceforge, but much better designed, and has a social component to it. I can follow the coders and projects that I admire or find useful, and I can also see what projects they are committing to or watching. Thus, it gives me a sort of leading indicator of what the alpha nerds and geeks find interesting. And what they find interesting is what you and I will be using in our jobs 5 to 8 years down the line. The generality of git, as mentioned in the previous entry is given as an example in the last link. It's of Raganwald, a well known Ruby coder and blogger who blogs on Github. Having a central place to commit and share code sorta defeats a mainstay of decentralized source control, but let's ignore that point for now, and drink the github kool-aid
http://www.github.com/
http://github.com/raganwald/homoiconic/tree/master/2008-10-30/thrush.markdown
GitTorrent
Along the same lines, someone combined git with bittorrents. Whoot.
http://www.advogato.org/article/994.html
SUP friendfeed
I'm personally not as excited about SUP as I don't mess around with feeds that much. But it claims to cut down on bandwidth for servicing feeds
http://blog.friendfeed.com/2008/08/simple-update-protocol-fetch-updates.html
Sinatra
If you thought Rails was lightweight, Sinatra blows it out of the water. While there have been other micro-frameworks for web apps, sinatra takes the cake in my opinion. It doesn't take very much at all to get something up and running with sinatra. So given the amount of prototyping work that the lab does, it helps to just get something demoable up. If you wanted to continue with it, sinatra runs on pretty solid web server, and you can optionally switch it out also. I'd recommend taking a good look at it, and brush up on your Ruby skills as well.
http://sinatra.rubyforge.org/
Clojure
Clojure is a lisp dialect in a JVM. I've heard some good things about it, but I haven't really tried it out myself, so I can't speak on the merits of Clojure. However, as the second link below wonders, could Clojure be to concurrency orientated programming as Java was to OOP? I've talked about Erlang in the past, and it defn has some amazing traits as a programming language, barring the syntax.
http://clojure.org/
http://bc.tech.coop/blog/081201.html
As for actual programming languages I've been messing with, there are three. Erlang, Javascript, and Lua. I'll only talk about the last one--and I only started messing with it because of LÖVE.
LÖVE is an "unquestionably awesome 2D game engine"
More akin to Pygame in Python than to Shoes in Ruby, Love lets you quickly build a game, but still stay within the realms of programming. The reason why I find it worth mentioning are the merits of Lua. It's a basic interpreted language, but it's embeddable into other languages, and its total size is pretty small ~200k or so. This make it ideal to be used in embedded systems. In addition, it's one of the faster interpreted languages out there, and with LuaJIT (on the JVM), it's even faster.
http://love2d.org/?teej
Mozilla Weave and Prism
Google Chrome
While I'm sure the lot of you have heard about Google Chrome, what's interesting to me is in relation to the direction that Mozilla, and also Adobe Air have been trying to move towards: treating web applications like desktop applications. Not only will they be easy to install, and easy to maintain, but they afford easy collaboration with others. And with the maturity of Google Gears, being offline is not a problem now either. While there are still a couple bastions where pure desktop applications reign, such as gaming, I think we'll find that the web app style development to be more pervasive for desktop apps.
http://labs.mozilla.com/2007/10/prism/
http://labs.mozilla.com/2007/12/introducing-weave/
http://www.google.com/chrome
SVG and application development
I don't know that SVG will be the future of application development or not, but I know that the current html and css constructs were meant for documents. Web developers are actually rebending those tools for application needs. While it's useful to think of the web as a collection of resources and document--it makes for a scaleable app--the actual page elements are still stuck in document-page speak. It would make it easier for app development to have their own app-specific constructs. SVG may or may not help in that regard
http://www.sitepoint.com/blogs/2008/12/22/svg-is-the-future-of-application-development/
Stackless Python, PyCUDA
There's lot of people trying to find suitable languages for our multicore future. I'm not so sure that Erlang will be it. However, functional programming concepts are going to make a comeback, if not already. Python is poised to be ready as being able to handle concurrency through stackless. Some people are experimenting with using Python to access the new Nvidia CUDA hardware architecture.
http://www.stackless.com/
http://mathema.tician.de/software/pycuda
Gnip Central
Gnip central acts as a data middle man. Often times, getting through the API sucks for various reasons, and having a middle man that either converts that data for you, makes it available, or converts it into a push model instead makes it convenient. It's an interesting niche, and I see this is as a perennial tar pit of data portability.
http://www.gnipcentral.com/
New York Times API
New York times is probably the more forward thinking out of all the newspapers when it comes to the web. Who else do you know that has released an API?
http://developer.nytimes.com/docs/movie_reviews_api?authChecked=1
-----
Hi all.
Well, after starting work at Frogmetrics last May, I got really busy writing code, learning about business and startup related things, and absorbing sales and marketing stuff, that I simply read a lot less. There was also less tech news going on that I felt was significant. When there's no significant news, the echoes become pretty loud in the echo chamber. Since I didn't hear anyone say anything about it, I figured no one read nerd time. And since I was reading less, I became more intellectually lazy. Hence the 10 month silence on nerd time.
But about a month and a half ago, I got in-person complaints that nerd time was no longer being sent out, so here it is reinstated. Some of these might be old news, but it's what I collected and found was significant over the last couple of months. And what the hell, old news in the tech world takes a while to get to the research lab world, so hey, this might be new to you. This time is mostly about source control and languages. I have other things I'm playing with that might be of interest, but will reveal them as I mature them.
Git the decentralized version control
Decentralized version control isn't anything new, but its adoption is. Git is pretty powerful. I don't go into all the reasons why. You can read about it in my post here. But on a deeper level, git is essentially a versioned filesystem. In fact, what's most interesting about it is how general it is and how you can use it for things other than version control. You can use it to synchronize address books, remote deploy code, or even as a basic wiki or blog.
http://git-scm.com/
http://whygitisbetterthanx.
http://eagain.net/articles/
Github a social network for developers
Github is like sourceforge, but much better designed, and has a social component to it. I can follow the coders and projects that I admire or find useful, and I can also see what projects they are committing to or watching. Thus, it gives me a sort of leading indicator of what the alpha nerds and geeks find interesting. And what they find interesting is what you and I will be using in our jobs 5 to 8 years down the line. The generality of git, as mentioned in the previous entry is given as an example in the last link. It's of Raganwald, a well known Ruby coder and blogger who blogs on Github. Having a central place to commit and share code sorta defeats a mainstay of decentralized source control, but let's ignore that point for now, and drink the github kool-aid
http://www.github.com/
http://github.com/raganwald/
GitTorrent
Along the same lines, someone combined git with bittorrents. Whoot.
http://www.advogato.org/
SUP friendfeed
I'm personally not as excited about SUP as I don't mess around with feeds that much. But it claims to cut down on bandwidth for servicing feeds
http://blog.friendfeed.com/
Sinatra
If you thought Rails was lightweight, Sinatra blows it out of the water. While there have been other micro-frameworks for web apps, sinatra takes the cake in my opinion. It doesn't take very much at all to get something up and running with sinatra. So given the amount of prototyping work that the lab does, it helps to just get something demoable up. If you wanted to continue with it, sinatra runs on pretty solid web server, and you can optionally switch it out also. I'd recommend taking a good look at it, and brush up on your Ruby skills as well.
http://sinatra.rubyforge.org/
Clojure
Clojure is a lisp dialect in a JVM. I've heard some good things about it, but I haven't really tried it out myself, so I can't speak on the merits of Clojure. However, as the second link below wonders, could Clojure be to concurrency orientated programming as Java was to OOP? I've talked about Erlang in the past, and it defn has some amazing traits as a programming language, barring the syntax.
http://clojure.org/
http://bc.tech.coop/blog/
As for actual programming languages I've been messing with, there are three. Erlang, Javascript, and Lua. I'll only talk about the last one--and I only started messing with it because of LÖVE.
LÖVE is an "unquestionably awesome 2D game engine"
More akin to Pygame in Python than to Shoes in Ruby, Love lets you quickly build a game, but still stay within the realms of programming. The reason why I find it worth mentioning are the merits of Lua. It's a basic interpreted language, but it's embeddable into other languages, and its total size is pretty small ~200k or so. This make it ideal to be used in embedded systems. In addition, it's one of the faster interpreted languages out there, and with LuaJIT (on the JVM), it's even faster.
http://love2d.org/?teej
Mozilla Weave and Prism
Google Chrome
While I'm sure the lot of you have heard about Google Chrome, what's interesting to me is in relation to the direction that Mozilla, and also Adobe Air have been trying to move towards: treating web applications like desktop applications. Not only will they be easy to install, and easy to maintain, but they afford easy collaboration with others. And with the maturity of Google Gears, being offline is not a problem now either. While there are still a couple bastions where pure desktop applications reign, such as gaming, I think we'll find that the web app style development to be more pervasive for desktop apps.
http://labs.mozilla.com/2007/
http://labs.mozilla.com/2007/
http://www.google.com/chrome
SVG and application development
I don't know that SVG will be the future of application development or not, but I know that the current html and css constructs were meant for documents. Web developers are actually rebending those tools for application needs. While it's useful to think of the web as a collection of resources and document--it makes for a scaleable app--the actual page elements are still stuck in document-page speak. It would make it easier for app development to have their own app-specific constructs. SVG may or may not help in that regard
http://www.sitepoint.com/
Stackless Python, PyCUDA
There's lot of people trying to find suitable languages for our multicore future. I'm not so sure that Erlang will be it. However, functional programming concepts are going to make a comeback, if not already. Python is poised to be ready as being able to handle concurrency through stackless. Some people are experimenting with using Python to access the new Nvidia CUDA hardware architecture.
http://www.stackless.com/
http://mathema.tician.de/
Gnip Central
Gnip central acts as a data middle man. Often times, getting through the API sucks for various reasons, and having a middle man that either converts that data for you, makes it available, or converts it into a push model instead makes it convenient. It's an interesting niche, and I see this is as a perennial tar pit of data portability.
http://www.gnipcentral.com/
New York Times API
New York times is probably the more forward thinking out of all the newspapers when it comes to the web. Who else do you know that has released an API?
http://developer.nytimes.com/
Subscribe to:
Posts (Atom)