BrainBlitz.org

March 23, 2010

AS3 A* pathfinding demo, with primitive multi-unit avoidance

Filed under: Programming — Anthony @ 1:29 am

And here I thought I was doing good because I had basic pathfinding implemented. Pffft. Turns out, that is only half of the story. The other half is unit coordination.

A* works very nicely, as long as the walkable/unwalkable cell states are at least somewhat permanently so. But what happens when you have, say, two units, getting all up in each-other’s grill? With A*, you find the path, then set the units on their way. Along the way, one may invalidate the path of the other. You can, of course, be performing collision detection en-route, and repath a unit if it encounters another. This is what I did in the demo on this page. The problem is, this direct approach opens a huge can of complicated worms. The system as a whole is so dynamic, that trying to handle all of the possible “race conditions” and circular results inevitably produces quite the code quagmire.

Here’s the actual demo. Click to create a tower “character.” Control-click to reinitialize the whole thing.

It won’t take much playing with it to realize that it is very, very broken. Characters will freeze as their states become invalid. Characters will be retarded. Sometimes the whole darn thing will freeze. (No code this time… it’s simply a nightmare, what-with all of my experimenting.)

 Not that you can’t make an acceptable algorithm using the straight-forward approach that I have here for simple applications, but I’m aiming a little higher for my final “product,” and most likely will take a step backwards in progress and work on more elegant solutions.

Here’s a rough outline of what’s happening in my code:

  • Unit starts in sleep mode, searching within its site range for entities from a different (“enemy”) group.
  • If enemy unit is found, build a list of all open cells adjacent to enemy. 
  • Pick closest enemy-adjacent cell that is open, and run A*.
  • Check for collision with other units on frame.
  • If collision, modify A* map with other character’s cell as unwalkable, recalc path, and revert A* map to prior state.

So, where do the issues come in?

One example is when the characters go into a collision state, and may respond in a way that keeps them in a collision state (i.e. they both move to the same cell to avoid the collision). This often results in “stuttering,” where the solution to the collision puts them into a collision for which the solution puts them back into the original collision. This could be handled in a couple of ways.

1. Have the first unit (#1) to detect the collision send a message to the other unit (#2) to ignore it (#1).
2. …sorry, I forgot what the other idea was while writing the first. I’m tired.

I’ll spend a little more time seeing if I can get an acceptable algorithm with the straight forward method. Otherwise…

I’ve got my reading cut out for me.
Amit’s Notes about Path-Finding – the pathfinding Bible? (Look at the rest of the site too)
Gamasutra: Coordinated Unit Movement - by Dave Pottinger (developed AI for Age Of Empires)
Gamasutra: Implementing Coordinated Movement - also by Dave

Also relevant:
AS3 data structures library (requires CS4, I believe) – at the moment I’m only using singly and doubly linked lists, but as I take a step back, I’ll probably end up using a lot more from it.
Cute lil’ character sprites by Karura

  • Print this article!
  • Digg
  • del.icio.us
  • Facebook
  • Google Bookmarks
  • StumbleUpon
  • Yahoo! Bookmarks

January 11, 2010

Post Adderall – Year of the Motivational Famine

Filed under: Adderall — Anthony @ 6:06 am

So it’s been about a year since I said goodbye to Adderall. And it has been one @%^@%! boring year. Every now and then I manage to get caught up in something for a few days – but never have the oomph to follow through and really create. Oh how I miss my old productive self.

I’ve come to the painful conclusion that I might actually have to go through an unpleasant re-training process. My brain became so accustomed to effortlessly cruising along, fueled by the little magical orange candy for $30/month, that it seems to have forgotten what real effort is. Now I mentally recoil at the thought of making myself DO something.

So I haven’t  spontaneously re-awakened after a year (@#%$!); I guess it’s time to be systematic about it. Set some goals or something (recoil! recoil! recoil!).

October 11, 2009

The Magical Pathfinding Brain

Filed under: Blogorrhoea, Bloody Cool — Anthony @ 12:54 am

I was watching an 18 month old walk around yesterday. Since I’ve been obsessed with pathfinding lately, I couldn’t help but be amazed at how, with no apparent effort, a toddler could navigate through a room full of furniture, getting where he wanted to go, generally along the shortest path.

And so I started thinking – how DO we actually perform a complex task such as finding the shortest path? At first glance, there is no answer really, “we just see it, it’s obvious.” But of course, something very complex IS happening, in the unconscious nether regions of the brain.

I think the first step in approaching the problem is to remove the visual sense, as it’s a distraction. The eyes bring information from any given scene in, but the visual sense doesn’t actually have anything to do with the actual pathfinding computation. Once the “scene” is in the brain, it exists as some sort of model, described by the brain’s fundamental language, and completely hidden from our conscious mind.

Another way to think about it is that the visual representation is simply a manifestation of the model that is in the brain. You can close your eyes and visualize the scene, and find the shortest path in your “mind’s eye,” but the work isn’t being done in the “mind’s eye,” it’s simply one view of the data residing elsewhere in the brain.

For me, getting rid of the visual sense makes things much easier to work with, because understanding what the sensation of vision actually is, and how it relates to our self-awareness, is kind of an intractable task. But now it’s out of the way!

So we’re left with trying to understand the technical details of how our biological computers solve the shortest path problem, which is far more approachable.

The next problem is – how is the model represented, fundamentally, in the brain? The brain obviously has it’s own, innate language. It has nothing to do with spoken language – a person who was raised in complete isolation (therefore had no concept of language) will still find the shortest path!

Of course, once you figure out the language of the brain, you now have to find out the rules by which it manipulates the data. If the language was binary, then the manipulation would be the logic gates, based on transistors (neurons).

But, as far as I know, we have no idea what the innate language of the brain is, or the rule-set by which it processes data. I imagine it is similar to trying to visualize the 4th dimension. I don’t remember which greek philospher/scientist it was, but he thought he’d proved the fourth dimension can’t exist, because all dimensions much be mutually perpendicular to each other. So he thought, if you take a stick, and lay it across another stick so that they form a cross, you have two dimensions. If you take a third stick and hold it perpendicular to the first two sticks, you have a representation of three dimensions. His proof that no more dimensions could exist was simply that you can’t add another stick that is mutually perpendicular to the first three.

What the fellow didn’t understand, however, was that our brains, never having encountered a fourth dimension, simply can’t comprehend it. It is like someone blind from birth trying to imagine what “red” looks like. That person can’t even begin to imagine it, because his brain has no concept of color, having never experienced it. Our physical world that we live in is 3-dimensioned, and so that is all our brain can comprehend. The fact is, in reality, there can be an arbitrary number of sticks, all perpendicular to each other. Don’t go trying that, of course. : )  For whatever reason, the physical state of the universe restricts our experience to 3 dimensions.

My point in going into that tangent was – I suspect that the language and processing of the brain might be genuinely beyond comprehension.

But that doesn’t mean it’s not solvable! Mathematically, working with 4 dimensions is only slightly harder than working with 3 (mainly because the equations get much longer). Just because we can’t comprehend the fourth dimension doesn’t mean we can’t work with it. Similarily, just because we might not ever comprehend how the brain works, we can still understand it, and work with it.

And figure out how it solves problems like finding the shortest path.

But who knows, maybe I’m wrong. Heck, maybe the brain works in binary. I kind of doubt it though - I imagine the brain does not even have a discrete alphabet forming it’s language, but rather a fuzzy, statistical alphabet. Maybe the answer will be found in quantum mechanics.

The last  observation has to do with artificial intelligence. So far, we haven’t been able to work with the 4th dimension (although it has been indirectly observed, as massive objects like the sun affect it by gravity). Indeed, it seems to be beyond the realm of our physical capacity (not capability, capacity) to work with it. In the same way, maybe it’s beyond our physical capacity to reproduce what the brain is doing.

That’s a hard chunk to swallow, but – we’ve observed the effects of gravity upon light via the 4th dimension, just as we’ve observed the effects of the brain’s operations.

So it maybe creating AI IS an intractable problem. That is – it’s not that the solution is difficult; it’s simply not possible.

Of course, again, maybe it all is just the biological equivalent to binary and transistors, in which case AI is inevitable (if humans are around long enough to figure it out).

In that case, maybe, when I find my way through an obstacle course along the shortest path, my brain actually applies a grid to the scene, and runs A* on it. : D

October 9, 2009

AS3 A* pathfinding class

Filed under: Programming — Anthony @ 6:26 pm

UPDATE: newer demo and source at http://www.brainblitz.org/anthony/as3-pathfinding-and-game-source.

Here is a* (a star) again, a little further along. Download: http://www.brainblitz.org/Misc/astar/v1.0/AStarMap1.0.zip

 Instructions: drag to fill squares, shift-drag to erase, space to run, r to clear all cells.

If you play with it, you’ll notice that the path always veers slightly into concave “barricades.” Some times it even just seems to arbitrarily wander off course by one cell, when it should be going in a straight line.

Why? The g cost of a diagnol movement is supposed to be 1.4 times the cost of a “straight” movement. I left that out of the algorithm for 2 reasons:

  1. For reasons I haven’t quite figured out, it runs 3 to 4 times faster without it.
  2. The imperfect solution almost looks more natural, with a little bit of random-ish looking meandering.

Here are a couple of examples of some of the quirks:

Speedwise, I don’t know what is typical for A*, but in Flash player, the time varied from 12ms to 23ms, the latter for very concave maps. In comparison, the graphics usually registered 0. So I’m sure there’s tons of room for improvement.

Class AStarMap

  • gridWidth
  • gridHeight
  • AStarMap(_gridWidth:int, _gridHeight:int)
  • setEndPoints(originX:int, originY:int, destX:int, destY:int)
  • solve():Array
  • getPath():Array
  • getCell(xx:int, yy:int):Object
  • setCell(xx:int, yy:int, cellType:int)
  • toggleCell(cellX:int, cellY:int)
  • reset()

Typical usage:

   var map:AStarMap = new AStarMap(20, 20);
   map.setCell(2, 4, map.CELL_FILLED);
   map.setCell(3, 4, map.CELL_FILLED);
   map.setCell(4, 4, map.CELL_FILLED);
   map.setCell(5, 4, map.CELL_FILLED);
   map.setEndPoints(2, 2, 18, 18);

   var solution:Array = map.solve();

The returned Array is an array of cell objects. Each object has the following properties:

   cell.x
   cell.y
   cell.parentCell
  

Note that this class does NOT address graphics: it is purely “math space.”

« Newer PostsOlder Posts »

Powered by WordPress