Print

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

[Mikademus]

I'd even bet that Toady developed his own pathing algorithm for DF instead of using A*.  He invented his own liquids engine.

Comparing apples and hand grenades, baby. I don't think there is a standard liquids engine so he'd more or less have to roll his own there, but to be brutally frank, he'd have to be pretty stupid to not use A*since that IS the most efficient pathing algo developed. It is the industry standard solution and Toady can't improve on it (if you're not a programmer don't bother arguing against this statement).

[Andir]

I'd even bet that Toady developed his own pathing algorithm for DF instead of using A*.  He invented his own liquids engine.

Comparing apples and hand grenades, baby. I don't think there is a standard liquids engine so he'd more or less have to roll his own there, but to be brutally frank, he'd have to be pretty stupid to not use A*since that IS the most efficient pathing algo developed. It is the industry standard solution and Toady can't improve on it (if you're not a programmer don't bother arguing against this statement).

I am a programmer and yes, A* is quick... but I don't think Toady uses it.  I'm pretty sure I remember reading a while back that he doesn't.  The problem with A* in it's native form is that it's a 2D algorithm.  There have been modifications to it to make it 3D though.  I know this because I looked into using this for a project I had at work.

Also, the first link on a google search will net you this PDF on a method called Flow Tiles: http://pages.cs.wisc.edu/~schenney/research/replication/flowtiles/flowtiles.pdf

Also, I hate correcting these types of statements, but A* is not the "most" efficient.  It's highly efficient at tile based worlds with finite boundaries using only one thread.

[Andir]

Found a quote.  He uses A* for general movement, but not for determination:

The dwarves themselves mostly move around with A*, with the regular old street-distance heuristic. The tricky part is that it can't really call A* if they don't know they can get there in advance, or it'll end up flooding the map and killing the processor.

http://www.gamasutra.com/view/feature/3549/interview_the_making_of_dwarf_.php?page=8

[texmith]

Reinventing the tried and true building blocks of game programming is hardly a trivial matter. Not that its necessarily 'hard', but its certainly a lot of work.

If you only knew how much code actually gets re-invented on a daily basis, I think you'd be amazed.  For instance, takea simple thing like Inventory management in games.  You have slots, weight, and possibly bags.  Developers have been recreating this system in just about every game that I've seen developed.

Recreating an existing system is hardly the same thing as inventing a new system. As you already pointed out, multithreaded programming involves more than just recreating the same algorithms for a new environment.

Just had the discussion about pathfinding in this thread: http://www.bay12games.com/forum/index.php?topic=28716.0

[profit]

Reinventing the tried and true building blocks of game programming is hardly a trivial matter. Not that its necessarily 'hard', but its certainly a lot of work.

If you only knew how much code actually gets re-invented on a daily basis, I think you'd be amazed.  For instance, takea simple thing like Inventory management in games.  You have slots, weight, and possibly bags.  Developers have been recreating this system in just about every game that I've seen developed.

Recreating an existing system is hardly the same thing as inventing a new system. As you already pointed out, multithreaded programming involves more than just recreating the same algorithms for a new environment.

Just had the discussion about pathfinding in this thread: http://www.bay12games.com/forum/index.php?topic=28716.0

Yeah but probably nothing else will bring performance of the game up to acceptable levels. So.. It may not be easy but without it the game will only get slower as more and more is added.  So... if toady is serious that he will never multithread the cores, either expect a massive amount of content dropped.. *in my experience this never happens as a developer would sooner take the scissors to their own eyes than to their beloved game*  ORRRRR  It lags worse with less dwarves and probably will get to the point embarking will be a 9 fps slideshow with degredation of 1 FPS per 3 dwarfs.

* addendium edit:

I am serious, ALMOST NO DEVELOPER WILL EVER CUT OUT THE FAT:

For example
Windows XP has 40,000,000 Lines of code
Microsoft windows vista has 50,000,000+ lines of code.

Name 3 features it dropped from windows XP in order to make it run faster.  Hell.. name one.

[Muz]

You can't compare it to Microsoft. Geez, Microsoft's goal is probably to use up as much CPU power as possible. A lot of other technologies do cut out the fat, look at encoding technology. MP3, especially. It's a good example between the balance of quality music and a small size.

[profit]

You can't compare it to Microsoft. Geez, Microsoft's goal is probably to use up as much CPU power as possible. A lot of other technologies do cut out the fat, look at encoding technology. MP3, especially. It's a good example between the balance of quality music and a small size.

MP3 Uses a TON more processing power than old PCM(Pulse Code Modulation) techniques.  and ENCODING a mp3 file uses massive amounts more.

It Sacrifices CPU time for smaller file sizes using a perceptual encoding method.  Great if you have alot of proccessing power and not much space, but not so good if you want to edit the music or encode it to another format.

Forgot to mention decoder length.
PCM decoders were this

Every 1/44000th of a second. Read 4 bytes.  Send 2 bytes to Right DaC, Send 2 Bytes to left DaC. Wait till needed again.

MP3 decoding is thousands of lines of code in length.

[Mikademus]

The problem with A* in it's native form is that it's a 2D algorithm.  There have been modifications to it to make it 3D though.  I know this because I looked into using this for a project I had at work.

Common misunderstanding. The normal implementation works on a 2D grid, but that doesn't make A* a 2D algorithm. Base your neighbour map on nodes and it can have any dimensionality.

[jaked122]

interesting, however if there are that many CPUs then each one would possess a much higher BITS per second rate, which assuming that it can be used correctly and that processors maintain backwards compatibility, then it could be with  500 Hz then you'd get as much or more work done, but I'm just a novice when it comes to this so...

[Align]

The problem with A* in it's native form is that it's a 2D algorithm.  There have been modifications to it to make it 3D though.  I know this because I looked into using this for a project I had at work.

Common misunderstanding. The normal implementation works on a 2D grid, but that doesn't make A* a 2D algorithm. Base your neighbour map on nodes and it can have any dimensionality.

but then, it's been frequently complained upon that pathfinding to items doesn't take z-levels and stairs into account, so it really is 2D in DF

[Mikademus]

The problem with A* in it's native form is that it's a 2D algorithm.  There have been modifications to it to make it 3D though.  I know this because I looked into using this for a project I had at work.

Common misunderstanding. The normal implementation works on a 2D grid, but that doesn't make A* a 2D algorithm. Base your neighbour map on nodes and it can have any dimensionality.

but then, it's been frequently complained upon that pathfinding to items doesn't take z-levels and stairs into account, so it really is 2D in DF

Yeah, if you implement the algorithm on a 2D grid you simplify the notion of a "node" which is convenient and beginner-friendly. But you also simplify away more generic and powerful solutions. And we're so engrained with the notion that pathfinding takes place on a 2D grid where each cell is accessed by x and y coordinates that it isn't even reflected over. And then you've made your foundations on that premise and it is an integral part of your game, and it's too late. And you have to code special layers around it to allow for levels, and eventually you have dwarf fortress.

[Footkerchief]

^^^ You have some reason to believe the main pathfinding wasn't gutted for 3D?

[Mikademus]

I remember a thread some months back (before the switch of forum software, or more accurately, before the switch to A forum software) where Toady (or if it was his lieutenant) mentioned a custom, tiered path finding solution.

But beyond that I'd be very surprised if the the built-in algorithm is 3+dimensional; it usually takes a combination of a decent degree of technical finesse and intrusive data structures.

[Nadaka]

I have been doing some thinking about the issue of splitting a game like DF into threads. One of the issues that crops up is that the work done for different aspects of the game is often massively lopsided. Flows and path find (or perhaps just path finding because flows actually use some path finding for resolution) would make up the bulk of processing, limiting scalability when one of those tasks maxes out an individual cpu.

One option that might work better for DF is to instead break the simulation up by physical areas, starting with one thread for each geographic tile in the play area.

[profit]

I have been doing some thinking about the issue of splitting a game like DF into threads. One of the issues that crops up is that the work done for different aspects of the game is often massively lopsided. Flows and path find (or perhaps just path finding because flows actually use some path finding for resolution) would make up the bulk of processing, limiting scalability when one of those tasks maxes out an individual cpu.

One option that might work better for DF is to instead break the simulation up by physical areas, starting with one thread for each geographic tile in the play area.

Or technically I believe every single task could be broken into its own thread with mutex locks or something similar when they could be addressing  the same actor. I do not think there is much tear down time on threads anymore so it could spawn the thread, run it, and end when the task ends.

Debugging programs like that become a headache though... and odd things crop up... like elvin archers that lagged my brothers open tibia server because their keep distance thread was starving.