Jump to content
  • Advertisement
Sign in to follow this  
  • entries
  • comments
  • views

A* and Water Part 5

Sign in to follow this  


Back to the A Star

Well, after doing research all weekend on steering algorithms, I have given up on the large rectangular area approach to storing nodes for a star.

It didn't offer enough benefits over a simpler dense mesh of waypoints. For instance, figuring out which 12x8 meter 'room' your character wanted to walk through doesn't help him steer around dynamic obstacles.

By switching to a dense ( 1x1 meter ) mesh of waypoints, I get several benefits :

1) most of the steering is handled by the mesh, instead of a separate system

2) I have a static & dynamic cost for each node->neighbor path. This lets me add & remove dynamic obtacles easily.

3) It's easier to annotate a dense area with tactical information or hints

...and, a new challenge - there are way more nodes now, from 24->400 for a simple level, taking more memory, and more pathfinding time.

So, to address this, I have changed to a system whereby each node takes only 20 bytes, is stored in a large 2d array, and has implicit neighbors.

One restriction is that the navigation area will be only 2d - so no going over or under a bridge. This restriction will make the astar faster and much simpler to implement.

We can still architecturally have anything geometry we want, but if we want the AI to navigate it, it will have to avoid over->under problems.

Had a good meeting today with my partner, and we have made some great design decisions. I'm really excited about both the ranged and melee combat systems.

Also, I have found a great programmer to help on coding, whom I met through GameDev. I'll let him announce himself if he wishes.

Water Part 5

To finish up on the water topic, I need to talk about the reflection and the water depth effect. Real water scatters light, and ends up tinting the water to some color - blue or green look good, so I wanted things under the water to be sort of fogged based on their depth. You can't use hw fog for this, b/c it is not defined in viewspace, but rather relative to the water plane.

Now, to do this really right, you would need to take into account the angle of the sunlight hitting the water, the angle of the viewer, the exact volume of water that the photons were travelling through to reach the eye, etc.

For a top down game, though, just using a texture mapped to the world Y axis seemed to work pretty well for me. The texture is blended in based on vertical distance from the water surface, scaled to some value so that it maxes out at some depth.

This way you can hide geometry under the water if it is far enough down or the water is dense enough, or just give a sense of depth via fading in the water color.

At level pre-processing time, I take each liquid triangle, create a bbox out of it, grow it a bit in x & z and bring the bottom of the box down vertically like 150 meters. Then I use this to find underwater triangles, and store them to be drawn later.

Then, after drawing the lit world, including the underwater triangles as normal, I then alpha blend in the liquid color, using a ramp texture :

This gives the 'underwater' effect. I could also map an animated 2d map to do a caustics type effect over the x & z axes, possibly skewed by the sunlight direction.

Lastly, the reflection. I didn't like the look of cubemaps, and I also couldn't get the fresnel working the way I wanted, so I decided to solve both problems with a gigantic cheat.

What I do is to have a simple 2d sky texture mapped to x & z in world space that is used for the reflection, and a circular gradient texture that acts as an overhead fresnel term. It makes the water near the character more translucent, and far from him more reflective. It approximates what fresnel & reflection would look like, but it's way easier to tweak to get it to look the way I want.

I could also scroll the sky reflection texture, but haven't bothered yet.

Well, that's it for the description of the water. Let me know if you have questions.
Sign in to follow this  


Recommended Comments

Good to see you made the switch to a grid of waypoints, seems much easier to work with. I was going to suggest that to you a while ago, I'm wondering why you didn't just go with that approach from the start?

The relativly massive increase in node count is a downer, but still 400 nodes isn't too bad. In the cities in my game I'm pushing close to 20k nodes just for humans...I have a seperate node map for vehicles which is simliar in size. Thank god I don't have to place them by hand ;-)

Your project is looking good as usual, can't wait to see the water in motion!

- Dan

Share this comment

Link to comment
I'm excited about your project quite a bit.

I thought if I could do the area approach, it would reduce the # of nodes to make searches faster, and then maybe I could be sloppier about speeding up the astar.

But, after looking at the steering headaches, and implementing a bit of it, it was clear that problem alone would be require tweaking for every level in the game.

400 nodes is just for a 20x20 test level. I expect my main levels to be ~128x128 or so, so thats 32k nodes, but at only 24 bytes a piece, that's less than half a meg, so...

Share this comment

Link to comment
btw, how do you break up the path planning work? Do you limit your dudes to a sliding window, or a certain # of nodes per tick or what?

I'm considering making my guys only explore like 24 nodes per tick, and only re-path every few seconds.

Share this comment

Link to comment
Well first I calculate the paths on a tile basis then I do a second pass where I determine the nodes on each tile the the actor/vehicle needs to visit. I check the bounds of the start->destination points in 2D space to minimize the tiles I need to use.

Plus I can get away with re-generating the paths for moving targets every few seconds or much less frequently than that in most situations without it being noticable due to the large open nature of the world. Still it's not as optimized as it could be.

One problem I'm having is generating the paths for the 5000+ civilians at startup...it takes a rediculious amount of time. There are a few different ways to avoid this that I'm currently investigating. I really can't go the route of GTA and not even consider civilians that are out of range of the camera. This is due to the high vantage points the player can have, and the strategic purpose the civilians serve....I need to have them persist even when the player is not around.

- Dan

Share this comment

Link to comment
Note that I'm speaking from a general lack of experience in AI, and A*.

You say you have implicit neighbours, does that mean that each node knows what an adjacent node is supposed to be? Because if so, one possibility for the over/under bridge situation is to, above the bridge, have only two nodes at the beginning and end of the bridge connect, and then under the bridge, connect the nodes on either side.

Btw, interesting hack for the water reflection...fairly case based, and really restricts your camera from going a bit isometric (the only real complaint I have about your game is the straight-down camera), but it's a neat idea!

Edit: You know, looking at some of your other screenshots, I'd recommend improving the dark spot of the reflection texture. Personally, I'd widen it, and possibly make it a bit smoother.

One problem I'm having is generating the paths for the 5000+ civilians at startup...it takes a rediculious amount of time.

You could, as part of the post-load processing, calculate the paths of x civilians at a time, such that ones near the player get their paths first and start going places, and keep expanding the number of civs per frame.

Share this comment

Link to comment
Good feedback on both counts.

Yes, I can certainly do over-under, it just complicates other parts of the code that have to figure out which is the nearest node, etc, and would require me to store the nodes in a hash and not in a simple 2d array.

I will keep the 2d array for now, and if it's an issue, I can add a 2nd 2d array for having 2 heights per spot, or more likely change it to a sparse hash instead.

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!