Tuesday 2 September 2014

Old dog, same tricks

Due to overwhelming demand to post again on my blog, I feel compelled to write about a conversation I had a few moments ago with a colleague. The conversation was nothing special, but I observed something that gave me pause for thought.

Before I continue, I should add some background here. I've been working in IT for (coughs) 25 years now. I've worked for only a handful of companies. Partly down to loyalty, partly down to laziness. But I think it's fair to say that I've had my hands in a number of pies. Mostly programming related, but I've managed projects, and even a small team in my time, as well as been under such large amounts of stress that could lead a lesser man to lose all of his hair.

And that leads me to my point about the conversation. My colleague was trying to explain to me that the changes made in one my teams code may cause problems at their end. A common conversation indeed. But what struck me was how very quickly I was able to grasp the reasoning behind why it could fail. It was particularly complicated, and involved the way the data got initially parsed from the database. I really don't need to go into detail, suffice to say I knew nothing of their codebase, but was able to very quickly effectively tell him what he was trying to put across. That then leads to a large sigh of relief all round as the problem is understood and we can address it in parallel.

I'm in danger of sounding like I'm blowing my own trumpet here, and I kind of am. But this isn't some "beautiful mind" moment here. This is that 25 years of experience coming together to analyze and evaluate what is going on. And that was the revelation. I am actually very good at my job, but in ways I hadn't really realized before. Had somebody from a different field (say an athlete) taken that call, they would have been totally unable to grasp it. Of course, many of my other colleagues (but not all of them) would probably have been able to derive the same outcome of the call. And that's what got me thinking.

What things come naturally in other careers after 20 years+ of service?

A plumber would probably be able to feel the screw connector in the dark, or immediately know the pipe to use with just a glance. And what about of we go into the world of music and arts. Had I been blowing a trumpet for 20 years, I would know to the millimetre the exact position to put each finger and how hard to blow. Imagine that. Just pure instinct.

Athletes... Do you "feel" the track? TV producers... Do you see multiple screens at once? Traders, do the numbers form shapes in your mind? Basically,  look out for those instinct moments. I'd love to know what they are.

Friday 27 June 2014

Assassins Creed Multiplayer - Some tips from the new kid in town.

I've taken my first dip into AC multiplayer with AC4, and it's been a rather rewarding experience. For somebody that fits in to the more "mature" category of gamers, it's perfect. Strategic and exciting at the same time. Unfortunately when you go online, you get confronted with people who play games as a way of life rather than a casual pastime. That makes life extremely difficult for the "noob"s among us. Particularly as you're kind of thrown into the deep end (although you should definitely go through the tutorials).

But here are some things I've learned (mainly from Wanted) that I hope will benefit the newcomer. There's plenty online about this kind of stuff, but I wanted to put my play-style into the mix. Of course, this is my opinion/style, so it's up to you whether you follow it (or even believe it). Here's hoping it gives you some good ground rules.

Running - Save if for COD
As a rule, you don't run in AC. Assassination is a gentleman's game you see. The main reason for not running is that this makes you "high profile". That means that your attackers and pursuers get a nice big red/blue arrow above your head. You know that satisfied feeling you get when your target reveals themselves by running? Well, don't give your pursuers that luxury.

Naturally, I believe there are exceptions to that rule. But you be the judge of my statements below:

  • Go for that brisk jog if you have no pursuers, and your target is a long way off. Being high profile is irrelevant at this point because nobody's interested! Remember though to pull the reigns nice and early. I do see people that slow down as they round the corner to their target… Too late!
  • If you have multiple pursuers, it may pay to pick up your heels and run. This hopefully gives the "fortunate" assassin a 100 point gain when they land their steely blade in your cranium. But consider the alternative of sticking around, getting a possible stun on one pursuer followed by a contested kill from another pursuer. 300 points right there. Of course, that could all go wrong and some swine darts up from a bench. But in my experience so far, that's not happening often.
  • Point starving. This is unlikely in your salad days of AC4MP, but if you have a chunky lead with one minute to play, there's a really good chance you'll have 3+ pursuers on you (and I believe the pursuers would be at the top of the scoreboard as well). Therefore, if it takes a minute to catch you for a measly 150 points, you can die quietly contented that the Animus will regenerate you and you'll still have that juicy lead. But like I say, this required you to get a hefty lead, and that ain't gonna' happen now is it?

Abilities - Keep it simple, stupid.
You know, I've been tinkering left right and centre with abilities and I have yet to be really comfortable with a load-out for a given situation. The capacity to aim some abilities can be very confusing as well. As a youngling, I highly recommend Disguise and decoy/bodyguard. Decoy can fool even the best, meaning a knuckle-cracking 200 point stun, or even a focus kill. You can (and should) play with other abilities. I would suggest spending each session getting the hang of one ability at a time.

Target Identification - Arrrrrrrgggghhhhh!!
Lord above this is one that could send you screaming out of the house and shouting profanities at passers by (please remember they're not targets though). I know I'm not alone in finding this the hardest piece. But I do have a few methods I keep in my pocket (remember, I'm all about Wanted, so it differs slightly in other game types).

  • If you don't know by now, your indicator turns blue when you have line of sight to the target. This means (and listen carefully) that there are no obstructions between you and the target. It has nothing to do with which way you're facing, or where your camera's pointing. If you're stood still, and the light goes blue then if nothing's happened in front of you… Guess what? THEY'RE BEHIND YOU!
  • The targets portrait gets larger and you hear heavy heartbeats when they're close.
  • So… Before spamming the assassinate button, double-check that the blue ring is full and that the target portrait is nice and large. An amusing school-boy error I used to suffer was being absolutely convinced I'd spotted my target, pursued them and dealt the deadly blow. Only then did I realize they'd buggered off somewhere else too far to even stun me! That poor civilian will never see his family again. But he does appear to have a large family, so I think it'll be ok.
  • Here's a tip. After playing for a while, you'll get the hang of how the compass gets larger as you approach, and then pops blue as you round a corner. So rather than carrying on towards your target, stop just before you expect them to appear in line-of-sight. If you wait, they may walk into sight for you. This saves you turning a corner into a mass of NPC's and being clueless as to which one it might be. Basically, approach corners carefully.
  • NPC's never go through chase breakers. If you're in one, feel free to spam the assassinate/stun button. Indeed, if you see somebody coming out of one it's worth doing the same.
  • Not sure who your target is in a blend group? Try deploying a decoy at any target at all. If you're lucky (and they're foolish), they'll blind panic the stun. They are now high profile, making for an instant L2/LT lock and kill. Enjoy.
  • Not sure if this fits into this section or scoring, but be prepared to score low in the early days. Two main reasons:
    1. You stick out like a sore thumb while you stand or creep around corners trying to get line-of-sight identification. This makes you tasty fodder for pursuers, as well as having a big sticker saying "I'M LOOKING FOR YOU" to your targets.
    2. Because of the above, people more experienced than your good self will boldly fly in and poach your target. How very inconsiderate. You then "Finish your target" with a boot only to find that's made you high-profile and there's a hook up your arse. Sorry, thems the breaks.

Consider "Vision" as a loss streak. It'll cheer you up as you're able to spot your target from a long way off and they glow a lovely "I'm about to die" blue.

Scoring - Take a deep breath.
Here's where the noob suffers. The Prestige player will have all sorts of wizardry at their disposal to finish off/disable their target, whereas you might have some blunt knives and a few coins to throw around. It's not fair, it really isn't. But go to bed dreaming of crafting a smoke bomb, and one day it just might happen! For now, you need to take slow approaches to identify your target and try not to get spotted. But here's some tips I've picked up so far.

  • Did I mention not to run? Knowing me, I probably wrote a whole section about it. It dents your score, and even if you do get a kill, it might be contested, making you immobile for a few seconds. That allows some other chump a focus kill.
  • Right, now you know how not to be a chump, you can start scoring off the chumps yourself. If your target makes a contested kill in front of you, they're going to be disabled for a few seconds afterwards. Target them and approach them. You should aim for at least a 350 kill, plus a 50 point focus (at least that's what I do).
  • When you're warmed up to that idea, have a look around for an opportunity to join a nearby blend-group before delivering the fatal blow. You need to be in there for just a second, and you're in x2 territory. Ooh la la. And this situation happens a LOT (at least once a game in my opinion). So be ready to score heavily. You'll see the experts climbing walls for acrobatic kills on you in this situation (to go towards their variety bonus). I'm too thumb-clumsy right now for those kind of shenanigans.
  • Check out the "Corner Stun" on YouTube. If you know your target is following you, duck in behind cover. They can't see round the corner you've just gone round… But you can see them! 200 points = thank you.
  • Get the Determined Perk. I simply cannot get rid of this right now. Contested kills halve your score, and therefore halve your manliness. Don't allow it.

Other Nuggets

  • Don't be deflated if you get Loss Streak. I've watched quite a few matches on YouTube now, and it's not uncommon to see people go from Kill Streak to Loss Streak very quickly in a game.
  • Try the "Playground" mode which gives you infinite time to wander around on your own. You can test out your abilities then. Also, if you're very sad, you could learn the maps at your leisure. But who would be so sad?
  • By the same token, why not try and buddy up with somebody and try a few things out?
  • Set your expectations. Maybe I'm in a minority here, but if I see a lot of Prestige's on the roster, I'm not expecting much. I actually go into "practise" mode.
  • Where's your pursuer gone? He's probably above your head. Oh, and it's probably too late now to do anything!
  • As much as this is a game of skill, there's a luck element to it that can make or break a round. I remember coming second (which doesn't happen often) by 25 points. Yep, first place managed a ground kill in the dying seconds. What was worse is that I missed that very same ground kill as I was a few steps behind. Tell me that's not bad luck? But what goes around comes around, and make sure you dine out on the times you snuck a podium spot over a prestige. Don't think about the bad stuff. It's bad for the soul.
  • Maybe it's just me, but I rule out any thoughts of a good score on the first few matches of a session. I call it "getting my eye in", which is difficult if you already have a patch over the other eye. Arrrrrrrr!
  • Try this: Sit on a bench or stand by a wall. How much vision do you have? What are your blind spots? Maybe (just maybe) you will see a target in a similar position and can plan an approach they won't expect.
  • As much as I love Wanted, I'd also  recommend Manhunt to the newcomer. Now, you're either the hunter or the prey, but not both. That can help you focus on target id-ing without worrying about Charlie Scissor-Hands behind you.
  • Check out the Ubisoft AC multiplayer forum. You'll be pleasantly surprised by how… erm… pleasant they are. This is a community that actively encourages new players. As always, you get the odd flamer and argumentative little b*st*rd, but I've found it to be a really helpful experience.

And Finally,
Please please please let me know what you think of this write-up. I

Tuesday 21 December 2010

Dead Nation - PS3

Seeing as there's not much on the internet about Dead Nation, I thought I'd write a review from somebody that's been playing it for a good while now and would like to give some feedback for those thinking about getting it.

What's to say about the plot? Well, not much tbh. You turn up in an apocylptic city where some "virus" has mutilated all that live there and now you have to find the reason and the cure. Hmmmm.... So, there is a plot, but you might as well ignore it because that's not what this game is about.

Pure and simple, this game is about shooting and shooting and shooting at... ZOMBIES! You start out with a simple rifle with unlimited ammo, but a pretty crappy rate of fire. A nice feature that took me a little while to get used to is how you aim. You use R2 in a kind of 360 degree fashion to point at the desired direction. This ultimately means you can be running backwards, and fire forwards. It takes a little while to get used to, but I kinda like it.

As you work your way through the game, you reach checkpoints where you can upgrade your rifle or buy bigger jucier weapons. The flamethrower should give you some early enjoyment as you squeeze lit petrol towards the buggers. If the group are close enough together, they'll all set fire to each other. Marvelous.

In fact, that's the general premise of enjoyment on this game. You get to try out different weapons and get a real sense of satisfaction when you find the right "tool for the job". For instance, if large pack of zombies are making their way towards you in a narrow area (and there are a lot of large packs as you'll find out), stick a mine in their way. KABLOOM !!! Limbs everywhere. You can upgrade the mines to have multiple detonations as well. So the pack behind get given the same treatment. Sorry boys! And there are plenty of static objects that you can use to your advantage. There are cars, fuel barrels etc that will blow up if shot at and take out anything in a given radius. Some cars have alarms that you can trigger that will drive the undead nuts and they'll attack that rather than you. Their fate is sealed as the car alarm going off is basically a prelude to it going pop and taking the locals out!

You can blast your way at high speed through the level to a checkpoint gate, or kill everything that moves in the area and the side streets. I would definitely reccomend the latter, because there are hidden caches to be found, containing money, ammo and often armour. Cash is the key to upgrading your weapons. I made this simple mistake when playing 2-player with a mate first time and we ended up literally being unable to complete the last wave of level 3.

At this point, I should talk about the graphics. They're great. The mood is set really well. It's very dark (too dark sometimes imo) and the framerate doesn't drop when there are 30+ zombies making their way towards you. Clearly a lot of effort has gone in to the game engine and it shows. It's not gonna blow your mind, but it's definitely a satisfying setting.

Not too close sweetheart

The game also contains multiplier concept. This is probably more relevant once you've completed the game because it doesn't improve the cash you receive, which is basically what  you want to fulfil the urge to upgrade. The  multiplier can rack up to 200x-300x plus, only to be hammered back to 1x having taken a few close hits. I must admit I do fancy trying a few of the early levels again to see what I can achieve.

So on to some negatives. My first grumble is weapon selection. In the heat of battle, you often have to make a quick switch to (say) the flamethrower. You do this using the L/R buttons and it's near impossible to hear the woman tell you what you've got selected, meaning you have to look down at the weapon icon selected. You can sort of get away with this by remembering that the SMG is one to the right of your rifle, which is left of the flamethrower. OK, that works for a bit, but then you get a new weapon and the whole cycle changes. What would have been better is if you could assign certain weapons to triangle, square, circle and X. These are unused in the game.

It's also too easy to accidentally press L1 which will lay a mine or grenade or whatever. Possibly my ageing reactions are to blame, but the odd flare would pop out. Grrrr...

Checkpoints are a little long on occasion too. Particularly the last "boss" checkpoints. They make you clear a lengthy few standard waves before bringing in the big boys. It's annoying to have to bust a gut finishing one phase to begin working out the strategy for the heavy-duty fellas. And there is always a strategy to beat them, it's just you have to fail quite a few times to work it out. I don't mind that (it's part of the idea right?), they could (should) have made the first couple of waves a bit more straightforward.

But I think all of the grumbles could probably be resolved if you play enough. And that's possibly not going to happen. Once completed, there isn't going to be a lot to make you want to play it again. There is a 2 player online co-op and some global league tables on which you bolster the effort for your specific country. I think I made about 0.0001% difference for each level I completed. The stats were moving quickly for the USA (obviously) and Finland (the developers country!?). The UK (my country) was ranked 11th, and it did give me an initial urge to "help the cause". I don't think I made a single grain of difference mind you, so that was very annoying. Checking forums, those stats might have something to do with zombies killed as a ratio to the population of that country.

Arrgh, that car alarm noise is so annoying... Uh oh...

Final verdict: I bought this game for £7.25 (approx) as a Playstation Plus member (I think it's £9.99 standard). That is excellent value for money. It's a game you can pick up and play with a mate very quickly. It's a laugh at times, especially when the limbs go flying. For me, setting a car alarm off, and watching 'em run towards it, shake it and then explode is possibly one of the most satisfying gaming moments I've had in years. Not one for Christmas day with the kids, that's for sure. But perhaps when they've gone to bed ;-)

Friday 22 October 2010

Manhattan distance formula is (of course) flawed !

Hey again,

So my latest game creation will be using the A* pathfinding algorithm. In brief, A* works from it's starting point, evaluating each of the neighbouring squares and seeing how far away it is from the target. It picks the nearest one to the target. I've bolded "nearest" here because in gaming, calculating the distance to the target is a somewhat hot bed of potatoes (if that's a metaphor?). Let's look at an example:

Here we have a grid and we need to get from point A to point B. The A* algorithm sums up the cost of moving to an adjacent square (g-cost) and adds in the distance from that square to the target (h-cost). It does this for every square and moves to the square with the lowest value. There's a bit more to it than that (a great article can be read on it here), but the key problem we have is with how to calculate the h-cost.

We could use the Euclidean Distance, which is a pretty straightforward formula once you get your head round it, and obviously very accurate. But this involves using something that game programmers try and avoid like the plague. The dreaded Square Root !! Of course, using square roots in the example above would be fine. We're talking about 6 diagonal gaps to fill before we reach the target. But what about a bigger grid? Or even multiple start points with multiple targets? I hope you can see that it might not always be the first choice.

And here's where I bring in the Manhattan Method (or Manhattan Heuristic as it might be more appropriately called). All the Manhattan Method does is work out how many units horizontally and vertically it would need to move to get to the target.

Clearly it's not the quickest route, but because the same algorithm is being applied to all the adjacent squares to A, you can (hopefully) see that the one to the bottom right of A is going to return the best score. Why am I using units of 10? Don't worry about it for now, but read the A* article above and it should become clear why.

It's lovely and fast because no division or square root calculations need to be done. Everybody's happy... Right?

Well I thought I was until a rather strange thing happened when I put a wall in the way:

Now the squares to the right of A are not available and are hence their distance is not considered. I have diplayed above the two points with the lowest Manhattan distances. But which point do you think has a lower "Manhattan" distance above, Point 1 or Point 2? I hope you are thinking that it is point 2, and you'd be right. But I'm afraid you'd also be right if you picked point 1! Don't believe me? Well, let's take the number of steps inbetween point 1 and B:

As you can see it's 6 places (or 60 as I'm using units of 10 here). Let's look look at point 2:

Oh dear, also 60 units away. So depending on which order you work through the adjacent squares, you may end up with a rather skewed route towards your goal. I should point out that the A* algorithm still finds it's way to the target in this example, but it might take a rather skewed route!

So how do you get round this? Well, I am pretty sure this anomaly will only occour in situations where the source and the target are either vertically or horizontally equal. Therefore, the Manhattan Heuristic could penalise the straight route by a small number (eg 1).

Interested to hear others !

Thursday 20 May 2010

A Catmull Rom Spline (curve) Implementation in Java


Another little challenge for my gaming world was to create a smooth route for a given node (eg a soldier). Using an A* algorithm gives very awkward turns (ofter 90 degrees) between two cells. What would be nice is to make the soldier turn in increments between the two cells. The more increments you have, the smoother the turn.

Let's say you have two points p1 and p2. You would like to find the smooth curve point halfway (0.5) between them. In order to do this with a Catmull Rom Spline curve, you're also going to have to provide the point before(p0) and after (p3).

Here's the method:

    public float q(float t) {
        return 0.5f * ((2 * p1) +
                      (p2 - p0) * t +
                      (2*p0 - 5*p1 + 4*p2 - p3) * t * t +
                      (3*p1 -p0 - 3 * p2 + p3) * t * t * t);

So let's start with a one-dimensional curve. The four values:

p0 = 1
p1 = 2
p2 = 2
p3 = 1

We want a point a point halfway (t=0.5). Plugging this into our method call q(0.5f), it returns a value of 2.125. Smoothing further:

q(0.25) = 2.171875
q(0.5) = 2.125
q(0.75) = 2.171875

Lovely, so we could potentially break this up an infinite number of times, but that would clearly take an infinite of time to run. You'll want to play with your implementation

You're probably already wondering how this can be configured for a 2D (or maybe 3D) A* algorithm. It's very simple actually, you just need to perform the algorithm for the x values and y values (or indeed, z values) on their own. I'm including all of the source code below, and I'll leave you to figure out how you might implement a CatmullRomSpline3D (I hope you can see it's really easy!). There are three Java classes below. I had some issues pasting them in, so please separate them by each "package".

By the way, if this is the first point in your A* route, then you're not going to have a previous point, so specify p0 = p1 (ie double-up on the value). If it's the last point on your route, then set p3 = p2.

Using the CatmullRomSplineUtils class (below) I as able to create a much smoother path (above diagram) around a particularly tricky route. I also noticed that it is blindingly fast. I haven't given it a thorough soaking yet, but this 13 point route with 5 subdivisions (which amounts to 121 new points) did not register a single milisecond in duration.

I can see that this could be workable for a racing game. The computer car ai calculations can be quickly recalculated if it got knocked off course.

package catmullrom;

public class CatmullRomSpline {
    private float p0, p1, p2, p3;

    public CatmullRomSpline(float p0, float p1, float p2, float p3) {
        this.p0 = p0;
        this.p1 = p1;
        this.p2 = p2;
        this.p3 = p3;

    public float q(float t) {
        return 0.5f * ((2 * p1) +
                      (p2 - p0) * t +
                      (2*p0 - 5*p1 + 4*p2 - p3) * t * t +
                      (3*p1 -p0 - 3 * p2 + p3) * t * t * t);

     * Example implementation
    public static void main(String[] args) {
        CatmullRomSpline crs = new CatmullRomSpline(1f, 2f, 2f, 1f);

     * @return the p0
    public float getP0() {
        return p0;

     * @param p0 the p0 to set
    public void setP0(float p0) {
        this.p0 = p0;

     * @return the p1
    public float getP1() {
        return p1;

     * @param p1 the p1 to set
    public void setP1(float p1) {
        this.p1 = p1;

     * @return the p2
    public float getP2() {
        return p2;

     * @param p2 the p2 to set
    public void setP2(float p2) {
        this.p2 = p2;

     * @return the p3
    public float getP3() {
        return p3;

     * @param p3 the p3 to set
    public void setP3(float p3) {
        this.p3 = p3;

package catmullrom;

public class CatmullRomSpline2D {
    private CatmullRomSpline splineXVals, splineYVals;

    public CatmullRomSpline2D(Point2D p0, Point2D p1, Point2D p2, Point2D p3) {
        assert p0 != null : "p0 cannot be null";
        assert p1 != null : "p1 cannot be null";
        assert p2 != null : "p2 cannot be null";
        assert p3 != null : "p3 cannot be null";

        splineXVals = new CatmullRomSpline(p0.getX(), p1.getX(), p2.getX(), p3.getX());
        splineYVals = new CatmullRomSpline(p0.getY(), p1.getY(), p2.getY(), p3.getY());

    public Point2D q(float t) {
        return new Point2D(splineXVals.q(t), splineYVals.q(t));

package catmullrom;

public class Point2D {
    private float x, y;

    public Point2D() {
        this(0f, 0f);

    public Point2D(float x, float y) {
        this.x = x;
        this.y = y;

     * @return the x
    public float getX() {
        return x;

     * @param x the x to set
    public void setX(float x) {
        this.x = x;

     * @return the y
    public float getY() {
        return y;

     * @param y the y to set
    public void setY(float y) {
        this.y = y;

package catmullrom;

public class CatmullRomSplineUtils {
     * Creates catmull spline curves between the points array.
     * @param points The current 2D points array
     * @param subdivisions The number of subdivisions to add between each of the points.
     * @return A larger array with the points subdivided.
    public static Point2D[] subdividePoints(Point2D[] points, int subdivisions) {
        assert points != null;
        assert points.length >= 3;

        Point2D[] subdividedPoints = new Point2D[((points.length-1) * subdivisions) + 1];

        float increments = 1f / (float)subdivisions;

        for (int i = 0; i < points.length-1; i++) {
            Point2D p0 = i == 0 ? points[i] : points[i-1];
            Point2D p1 = points[i];
            Point2D p2 = points[i+1];
            Point2D p3 = (i+2 == points.length) ? points[i+1] : points[i+2];

            CatmullRomSpline2D crs = new CatmullRomSpline2D(p0, p1, p2, p3);

            for (int j = 0; j <= subdivisions; j++) {
                subdividedPoints[(i*subdivisions)+j] = crs.q(j * increments);

        return subdividedPoints;

    public static void main(String[] args) {
        Point2D[] pointArray = new Point2D[4];

        pointArray[0] = new Point2D(1f, 1f);
        pointArray[1] = new Point2D(2f, 2f);
        pointArray[2] = new Point2D(3f, 2f);
        pointArray[3] = new Point2D(4f, 1f);

        Point2D[] subdividedPoints = CatmullRomSplineUtils.subdividePoints(pointArray, 4);

        for (Point2D point : subdividedPoints) {
            System.out.println("" + point);

Monday 1 March 2010

PSP Downloads... What was I thinking?

I've just downloaded GTA: Chinatown Wars on my shiny new PSP 3000. I love the fact that you can make an impulse decision and get yourself a game in about 30 minutes (assuming a reasonable broadband connection). It's much quicker running from a memory stick too.

But then you realise something very quickly. You actually end up with nothing but data. No box, no disk, no instructions. Oh crap!

It's not a bad game, but I'm not really enjoying it. I'm finding it just a fraction too fiddly. The police are too easy to aggro, and the control is just too frantic. Many disagree, so I think I may have to bow to their gaming sage-ness. Age is inversely proportional to thumb dexterity it would seem.

And therefore, I now have nothing. I very much doubt I can get a refund based on a "I don't like it" argument. I can't e-bay it either. That's always been a staple excuse of mine that I would be able to get a bit back (sometimes 80% of the RRP) if things didn't work out. Now I'm just empty.

Blockbuster have stopped stocking PSP's and games because Sony's latest PSP-Go only does downloads (ie no UMD slot anymore!). They see this as a smack in the face for their sales and have taken the hard line. I'm tempted to adopt a similar stance. Maybe I'm old-fashioned, but my next purchase (over a tenner) is going to be on e-bay. I'll just have to curb my enthusiasm for a day or two and wait under the letterbox!

That will get Sony quaking in its boots ;-)

Wednesday 10 February 2010

A Maze Algorithm in Java

I had a good hunt around for a maze creator written in Java, but couldn't find one quite to my liking. So I wrote my own, using the Depth First - Recursive Backtracker method.

Download source my files here

First of all, I created a class that contains the details for each "cell" of the maze (GridCell.java). This contains the details required for each maze cell (which walls are up/down, and whether that cell has been visited yet).

Now on to the main code, my (MazeGrid.java). Hopefully, there's enough commenting on here to make it clear what it's doing, but just in case, here is the pseudo-code for the generateMaze() method:

  • Reset all cells in the grid ( resetGridCells() ).
  • Work out how many cells there are (width*height) and also create a last-in-first-out stack of visited cells.
  • Start at the top-left (y=0,x=0)
  • While there are still cells left unvisited (cellsVisited < width*height):
    • See if there are any cells that can be visited from the current cell that we have not yet visited ( unvisitedCellCanBeReached(...) ).
    • If there are cells we can visit, pick one at random ( getRandomUnvisitedCell(...) ), set the wall on the current side as down and move to the next cell. Add this next cell to the top of the stack, set it to "visited" and increase the visited count.
    • If there are no cells we can visit from our current location, then "pop" the previous location off the stack and move back there.
  • Once we've visited all the cells, I need to do a "cleanup". A slight flaw in my design means that if (say) a cells east wall is flagged as down (intact = false), then the cell next to it (on the east side) should have its west wall down (basically I've created double-strength walls). So the cleanup method knocks down any of these walls as well.
That's it. You can now call getGridCells() to get the array. If you want to try it out, download the MazeGenerator.jar file. It should auto-execute. It's got some other Java classes in there that I created quickly in Netbeans to allow a visual representation.

Have fun!