Help with smart random level generation

[The_Lizard]

Hi,

I'm trying to make a point click game, where you click the mouse in an area, and the character will walk to where you clicked. The tricky part comes in because I setup random level generation, so that the player gets a new map every time they play. I one MC for the level, which contains a grid of other MCs. Each section of the grid, or floor tile, makes itself into either 1 of 3 different patterns of floor, or an obstacle based on random integer when the game is loaded.

My question is, how could I make this so when you click somewhere, the character will find a path to the area that is clicked that bypasses any obstacles that could be in the way. Also, it should be able to determine if the area clicked is completely boxed off by obstacles and is impossible to get to.

I have been thinking about ways to do this for a few days now, and just can't wrap my head around a way to make this happen. Can anyone provide any idea, even just in pseudocode on how this could be possible?

Thank you very much

[TOdorus]

http://www.policyalmanac.org/games/aStarTutorial.htm

[--Fusiox--]

I'm not that good at Flash as a whole but I've had my own share of experience with tile-based world games. Since I don't have any actual code on me, I'll attempt to create some form of vage explanation:

*First, I'm pretty sure you have the actual movement of the character set up in a function. This function can't be so vague that it's essentially hard-coded (such as telling the computer to move the character 25 pixels to the left instead of a more code-dependent and better-working function of telling the computer to move the character one tile to the left). While pathfinding can be done using hard-code, I recommend taking the time to actually code your functions in a more stable and code-dependent way. It will make your life much easier when trying to figure out how to pathfind.

*Next, you need to create code that tells the computer the relative distance between the character and the tile the computer needs to move the character to. I'm no AI wiz, so I can't help you much, but one thing I can say is that A* (A-Star) pathfinding code which was probably addresed in the link above basically assigns every tile adjacent and diagonal to the character a numerical value. The closer the tile is, the lower its "F" value (F=G+H, G being the movement cost that it takes for the computer to move the character to any given location using the movement code [that's why I mentioned above to create a very sound movement function], H being the estimated movement cost that it takes for the character to get from the chosen spot to the final destination). The character simply chooses the tiles with the lowest F value to decide where to move. It's more complicated than I describe it to be, but a good tip is:
-Make your movement code dependent on the tiles themselves. This way when you assign the F, G, and H values to tiles, the computer can create a connection between moving the character and the F value of tiles dependent on the character's position.

It's a brainful, but I hope it will give you some ideas. Since you've already made the map and told the computer which tiles are passable and non-passable, it will be easier to do the pathfinding AI--simply tell the computer to ignore the impassable tiles when choosing which tile to move on, or give it a horrendorously high F value that will always be higher than any other adjacent or diagonal tile (such as its G value equalling 1000 or what have you).

Good luck!
-Fusiox

[The_Lizard]

Thank you very much, that was a very informative article.

[Son of Bryce]

Tonypa's got great Flash A*/tile-based tutorials, if you need an example of a Flash implementation.

http://www.tonypa.pri.ee/tbw/

[gambrinous]

If you look into implementing A* pathfinding you'll find it's easier to first implement breadth-first pathfinding (an equivalent system which is a bit slower). The only difference between the two is that instead of keeping an array of 'to-do' paths, you keep them in a 'priority queue' which is basically a data structure where they are kept sorted by distance.

When you get to that stage you'll find this AS3 data structure library extremely useful as it includes priority queues in AS3.

The good thing is that you get the same results with breadth-first vs A*, it's just more efficient with A*. So for my game at least, moving to A* is a job for later, when optimising