Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[malloc]

A* can actually be optimized by weighting it, and making it greedy. By prioritizing searches closest to the destination, you can actually reduce the number of nodes it checks. This is useful if you are just interested in finding a path, but not necessarily the best path.

The default A* will always find the shortest path to the destination, at the cost of being, on average, more computationally expensive.

But then again, it depends on whether or not you actually need the shortest path. Perfect path finding has that unfortunate side effect in games of being really predictable.

[fergus]

A* can actually be optimized by weighting it, and making it greedy. By prioritizing searches closest to the destination, you can actually reduce the number of nodes it checks. This is useful if you are just interested in finding a path, but not necessarily the best path.

Isn't that what A* is?

[malloc]

No, a default implementation of A * will always return the shortest path. If a path can be found.
You can see this on Dreadmullet's GIF, the nodes are expanded uniformly, based on distance to the destination. Since all sub solutions are kept at equal distance, the first found solution will be the shortest. I suppose you can call it greedy, on the basis that it does expand the more likely nodes first.

A weighted algorithm will search most direct path first, which means one can't be sure the first solution is the shortest one.

[fergus]

Since all sub solutions are kept at equal distance

I don't think this is actually the case, I think all solutions will have approximately the same (distance traversed+estimated distance remaining), but I get your point.

[malloc]

Yeah, I find it a little hard finding the right words sometimes. I never had any talent for that.

[Max White]

Although if, for example, you were making an AI to move through a maze, wouldn't it seem a little more realistic if you used a weighted algorithm, so that the actor attempted to move as the crow flies and made variations from that, rather than knowing what is the shortest path?

[MorleyDev]

A*#Weighted

Explains it and the animation there shows where it can look unrealistic ^^

[Siquo]

Adding plain 3D noise to a terrain yields... unacceptable results

Spoiler (click to show/hide)

But at least I've got the basics. Needs some stitching here and there, as well.

[malloc]

So you're working with voxel data? If you are, good job on the surface generator, are you using marching cubes algorithm or something?
Also, looks cool, even if you might have set the noise frequency a bit high. 

[Virex]

Adding plain 3D noise to a terrain yields... unacceptable results

Spoiler (click to show/hide)

But at least I've got the basics. Needs some stitching here and there, as well.

What are you trying to do that couldn't be solved with 2d-noise height maps?

[Nadaka]

Adding plain 3D noise to a terrain yields... unacceptable results

Spoiler (click to show/hide)

But at least I've got the basics. Needs some stitching here and there, as well.

What are you trying to do that couldn't be solved with 2d-noise height maps?

Overhangs, arches and caves.

[Virex]

Wouldn't it be easier to generate those via volumetric carving instead of 3D noise?

[malloc]

Using a combination of different noises you can get very interesting features. It also has the advantage of being very deterministic.

There is a interesting Nvidia article showing off procedural 3d terrain generation by computing and combining noise samples.

Edit:
You can look at it here: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html

[MorleyDev]

We've had talk for ages of specialised hardware for each part of logic slowly replacing the traditional CPU. As awesome as that would be, I have to wonder if it'll ever happen. We're already seeing something similar simply by how much logic can be put onto a good GPU if you really want to, and specialised physics processing units...

You can get "Random Number Generator" chips but outside of advanced physics true randomness isn't that important...

[Virex]

We've had talk for ages of specialised hardware for each part of logic slowly replacing the traditional CPU. As awesome as that would be, I have to wonder if it'll ever happen. We're already seeing something similar simply by how much logic can be put onto a good GPU if you really want to, and specialised physics processing units...

You can get "Random Number Generator" chips but outside of advanced physics true randomness isn't that important...

It depends on the customer really. As there is a shift going on from desktops to mobile systems such as pads and eReaders, price, energy usage and size become as important as raw power. If someone is willing to pay big money for dedicated physics hardware (maybe a company that does a lot of simulations?) then it will probably reach the customer market, but I doubt the customer market itself will be enough to get it.