Will Thimbleby

A* is a well known and popular shortest path algorithm. With the correct heuristic it is efficient and finds the optimal solution. Here’s a fun and simple Javascript implementation that makes use of the canvas element. The code is free (public domain) for anyone to use or improve.

The above demo lets you play with the algorithm. By clicking you can add/remove walls or drag the start (blue) or end (red) nodes. The shortest route is highlighted by a red line and the searched nodes are drawn from yellow to green by distance from the start node.

The options to the right of the map control how the path is calculated. Diagonal movement is considered as the same cost as straight movement, but the tweak diagonal cost toggle adjust the diagonal cost to be slightly more expensive so that nicer looking paths are preferred. This doesn’t alter the length of the found path only the number of nodes searched and the path’s appearance.

A tie breaker can be used to decided which nodes with the same estimated cost are preferred. Preferring new nodes is a very simple and efficient tie breaker. The prefer new nodes option toggles preferring new/old nodes, if old nodes are preferred then A* performs much worse especially for empty spaces. The dot product tie breaker is a different tie breaker that chooses paths that are closer to the straight line between the start and end for equal paths.

For more information on the A* algorithm and path finding I would recommend Amit’s A* Pages.

These were created by using A* repeatedly. Each shortest path found reduced the cost along that path, thus creating brighter yellow ‘worn’ paths. The paths are generated either using a random goal location from a fixed starting point or as part of a round trip A to random location to B.

There has been plenty of interest in MISC, that warrant some quick comments.

• The source code is now available here: MISC source (about 3000 lines of Java code and 350 of MISC). Hopefully you’ll find it useful. It might also be interesting/confusing to look at the bootstrap file.
• The mathematical operators now accept multiple operands like [+ 2 3 4 5]
• Yes I like square brackets (Smalltalk, ObjC) it saves the shift key
• Quoting is required in lamda/let because there are no special forms in MISC. This means that it is possible to write lambda, let and if etc. without macros and also to have the results of an expression provide the arguments for these functions, eg. [let [union '[a:3] '[b:4]] '[+ a b]] which is not possible to write in this fashion in Lisp, because in Lisp let is a special form and does not evaluate it’s first argument.
• Creating new things and exploring ideas are always important, which is what MISC achieves for me.

MISC has been a long time in the creation. It started when I got sick of XML’s lack of consistent structure and heavy markup. I wanted something consistent and clean like LISP but with a more general basic data structure. This was the initial spark “LISP with maps instead of lists”.

• [if [> 5 10] then:[+ 5 10] else:[- 5 10]]
• [let '[square:[lambda '[x:1] '[* x x]]]
    '[square 12]
  ]
• [take 20 [numbers from:0]]

After writing some example pseudo code to see what it would look like, I wrote a simple version in a couple of days. Since that speedy start the actual design with the complexities of a language have taken a very long time to finish. I changed the basic structure several times to fix major issues I hadn’t thought of and I switched the design from an eager language to a lazy language which I felt matched the base data structure of maps better.

I became interested in how rich metadata as basic part of the language and the source code could enable powerful reflective programming, like documentation built into source code. All these different ideas and designs added up and every time I thought “Would it not be easier if it just worked like language X,” I had to tell myself if it did there’d be no point in writing MISC. Thus the result is not a language for real-world use but one that I hope embodies many different unique and novel design decisions in a way that triggers thoughts and ideas in those that take the time to play with it.

What’s different and why you should be interested:

• Novel LISP-like language
• Homoiconicity (ie. source code that is data) using maps
• A great lazy data-language
• Cool stuff with metadata
• A metacircular– interpreter and syntax-colourer

Not only that; but it runs as an applet with some neat inline documentation: MISC

Just for fun here are a couple of applet based roguelikes I wrote a while back. The first is a reasonable example of a simple and concise roguelike. The second is an attempt at a roguelike with directional player facing, it also adds directional monsters, hearing and sprinting. The above-right picture shows an unknown monster sneaking up on the player from behind and an ant, above-right of the player, looking towards the player.

I hope these are somehow informative/fun for someone. The source code for both applets is public domain.

eWeek described the top 5 programming languages to learn (if you want a job) as:

• PHP
• C#
• AJAX
• Javascript
• Perl

Not the most exciting list. My top 5 languages to learn (if you want to learn something) are:

• Scheme — The essentials of programming without syntax. It also allows for some crazy metaprogramming.
• C — It’s everywhere, has become the defacto syntax, and it forces you to learn about manual memory management, pointers, arrays, bits etc…
• Simple assembly — Lets you deal directly with registers and interrupts. I learnt Z80 assembly but I would recommend learning PIC, AVR or MSP430 programming. It’s much more fun than it sounds and it makes you appreciate every other language out there.
• Haskell — Pure, functional, lazy and strongly typed. A head-job but it will stretch your thinking.
• Prolog — A declarative language, you describe facts and rules and hopefully Prolog does the rest.

The top 5 languages that I would like an excuse to learn are:

• Erlang — A process based language with lots of interesting ideas.
• Lua — An extremely light-weight and fast scripting language.
• Objective Caml — A statically typed functional language.
• C# — Java like but with some additional good ideas.
• Squeak — A language with its own OS and GUI!

Scripting with JavaScript in Cocoa is a brilliant way to add scripts and a language to your app. Even better it is extremely easy. My article is a great place to start. I’ve just updated it thanks to Jack Nutting who fixed a bug on Leopard.  

Two quick photos of demoing the calculator in India at TechFest. An estimated 50,000 people came.

The concept of content aware image resizing is to resize an image whilst preserving the important parts of the image. A very simple and neat method to do this was presented in a paper at this years SIGGRAPH, the superb results of which can also be seen in this YouTube video.

The trick involves removing least cost seams through the image instead of the evenly spaced columns or rows that scaling removes. All the details are in the very readable and clear paper. Unfortunately the idea was simply too neat to avoid tinkering with. Thus we arrive here. I’ve implemented the basics of the paper pretty much as is, using directional Sobel filters to calculate the cost of removing pixels.

The photo below is a good example of a photo that works with this technique.

This resizes horizontally to:

(content-aware vs. standard scaling)

and vertically to:

The content aware resizing creates much clearer shrunk images of the origninal preserving the houses on the right. Unfortunately this resizing doesn’t work well for most images, it works best for images with areas of detail and flat areas. Download it, give it a go and see what it can do. The application and source code (BSD Licence) are available for anyone to tinker with and improve.

There are obviously lots more possible things that could be done to this app. Including: suitability estimate based on the variance of the seam costs, image expanding, different weighting algorithms to choose for different images, pre-calculation and live resizing, and weight painting for areas of interest/disinterest.

If you find any nice examples or find a use for the source code let me know.

• Blue line: Total word count
• Red line: Edit position (bottom = end of document)

Next Page »