mrimer
Level: Legendary Smitemaster

Rank Points: 5411
Registered: 02-04-2003
IP: Logged

vittro wrote:
I've noticed something while playing DROD: brained roaches (or guards) do not pathfind towards stalwarts - only stalwarts do pathfind towards them.

Is this why DROD is so fast? I was trying to make every single roach pathfind to a stalwart and every single stalwart pathfind to a roach.

No, I think starting with multiple goals for a single pathmap wouldn't be any slower than always starting with the single (player) goal like DROD does now. It's possible it's fast simply because it's written in C++ (quick use of POD types in data structures) and we worked carefully to make the pathmap fast. That's just a guess though.

____________________________
Gandalf? Yes... That's what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now at the turn of the tide.

vittro
Level: Smiter

Rank Points: 489
Registered: 04-17-2005
IP: Logged

Is this how DROD does it? (quick mockup made in excel)



The top-left pathmap is a breadth-first search for one of the enemies (in red).
The bottom-left one is a breadth-first search for the other enemy.
The pathmap on the top-right is the sum of the two searches.

I see some problems with this, though... the paths created are not correct, there are many equal numbers and that could lead to strange behavior.
Also, considering I can have 200+ entities in a single room, this means I would have to run 200 breadth-first searches and sum all of them togheter.

Sounds slow..

____________________________
http://vittorioromeo.com

mrimer
Level: Legendary Smitemaster

Rank Points: 5411
Registered: 02-04-2003
IP: Logged

vittro wrote:
Is this how DROD does it? (quick mockup made in excel)

Yes, pretty much. DROD does perform an A* search. Take a look at "CMonster::FindOptimalPathTo" and "CMonster::FindOptimalPathToClosestMonster" in DRODLib/Monster.cpp.

I see some problems with this, though... the paths created are not correct, there are many equal numbers and that could lead to strange behavior.

We break ties by prioritizing certain movement directions above others, which you can study in the above methods.

Sounds slow..

Well, the proof is in the pudding. Computers have gotten pretty fast, and one turn of this for 200 monsters can be calculated pretty fast. You do see a little slowdown in cases like the stalwart-aumtlich battle in TCB. As you know, we perform the abovementioned dynamic game state snapshotting so that undo functionality can be fast. Of course, we do some clever tricks like not have a stalwart (etc) build a pathmap when it doesn't have any candidate targets in the room. Also, in some cases, like with Halph and the Slayer, it builds a path to the target, and then once that path is established, it doesn't need to recompute it each turn -- only confirm that the path is still available, and keep following it if so.

____________________________
Gandalf? Yes... That's what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now at the turn of the tide.

---

[Last edited by mrimer at 06-12-2012 09:06 PM]

TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

More to the point: DROD does *not* combine pathmaps at all. The source code is available, so you really should read through it if you're wondering how DROD does things... but realise that it may not be exactly what you want.

Brained monsters only use the single pathmap to the player (although there are multiple pathmaps based on the terrain-type different monsters use, like Water, Ground, Air, etc.) Each Stalwart builds its own pathmap, but only as far as it finds the closest monster to it (for example, if it finds a monster at 9 steps out, it won't bother checking 10 or more steps).

Also, consider what you want and how you're doing it. Why would you want to *sum* the values of these pathmaps? That would mean that if two entities were in a straight line from each other, then all the tiles in between those entities would have the same value. You don't want the sum... you want the *minimum*.

If you really wanted to do a pathmap to multiple entities though, then it's not really all that difficult. You'd start by adding the co-ordinates of all the targets you have to a stack, and marking those tiles on the grid as 0 steps. Then you'd add all the tiles adjacent to these, skipping any tile that has already been marked as 0. Then you go through those new 1 step tiles, adding all the tile surrounding them to be marked as 2 (providing they haven't been marked as a lesser number already). Continue until you run out of new tiles to mark. At the end, you have a completely finished pathmap that shows the fastest route to multiple targets.

mrimer
Level: Legendary Smitemaster

Rank Points: 5411
Registered: 02-04-2003
IP: Logged

TFMurphy, thanks for spelling out in every way what I've been hinting at in the above posts.

____________________________
Gandalf? Yes... That's what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now at the turn of the tide.

vittro
Level: Smiter

Rank Points: 489
Registered: 04-17-2005
IP: Logged

Oh, thank you both immensely. It is very clear now.



Bah, fixed. H&S effect!

____________________________
http://vittorioromeo.com

---

[Last edited by vittro at 06-13-2012 04:16 PM]

Briareos
Level: Smitemaster

Rank Points: 3516
Registered: 08-07-2005
IP: Logged

vittro wrote:
Bah, fixed. H&S effect!

np: Mogwai - Summer (Klute's Weird Winter Remix) (Kicking A Dead Pig (Disc 1))

____________________________
"I'm not anti-anything, I'm anti-everything, it fits better." - Sole
R.I.P. Robert Feldhoff (1962-2009)

vittro
Level: Smiter

Rank Points: 489
Registered: 04-17-2005
IP: Logged

Briareos wrote:

vittro wrote:
Bah, fixed. H&S effect!

Click here to view the secret text

×The 8 tiles surrounding Beethro not all having the value 1 kinda gave the problem away...

Click here to view the secret text

×Not to mention that without obstacles in the way all tiles n steps away from Beethro should have value n...

np: Mogwai - Summer (Klute's Weird Winter Remix) (Kicking A Dead Pig (Disc 1))

Oh, but I didn't fix it like that. Diagonal squares have a slightly higher value, so that enemies take more natural-looking paths.

Behavior is very similar to DROD.

____________________________
http://vittorioromeo.com

mrimer
Level: Legendary Smitemaster

Rank Points: 5411
Registered: 02-04-2003
IP: Logged

Here's basically how DROD scores each tile:

Score = Distance * 8 + (direction #)

Without looking again at the code, I can't remember the # given to each direction, but it was something like:

N = 0
E = 1
S = 2
W = 3
NW = 4
NE = 5
SE = 6
SW = 7

So, there is a distinct score for each movement direction, encouraging the lower-scored directions to take precedence, all other things being equal.

____________________________
Gandalf? Yes... That's what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now at the turn of the tide.

TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

mrimer wrote:
So, there is a distinct score for each movement direction, encouraging the lower-scored directions to take precedence, all other things being equal.

That's for FindOptimalPath, not for brain pathmapping though. And FindOptimalPath has a number of problems with it, not least being that it doesn't particularly care how it gets to a certain tile, which leads to some of the chaotic/random moves that Stalwarts make when pathfinding.

But since vittro's building a full pathmap and not just trying to find a single path to whichever monster happens to be closest, why change the pathmap numbers itself? CPathMap::GetRecPaths already has a method of breaking ties in a easy way that players are used to.

And vittro, you really should make more of an effort to read through and figure out what the DROD source code is doing. Look up commands if you don't know what they do. Read through the comments in the code, compare what the code says to how things work in game. You're already familiar with programming itself, so this shouldn't be that alien to you.

vittro
Level: Smiter

Rank Points: 489
Registered: 04-17-2005
IP: Logged

Just a quick update on what I've accomplished.

I now have easy-to-create pathmaps. You can "subscribe" entities to pathmaps, and they automatically take care of them during calculation.
I've created (so far) a "friendly-ground" pathmap and a "enemy-ground" pathmap.
Entities such as Beethro and Stalwarts are subscribed to the "friendly-ground" pathmap, and target the "enemy-ground" pathmap.
Entities such as roaches and roach-queens do the exact opposite.

I've done some profiling, and the game is acceptably fast on 100x100 rooms, with any amount of entities.
Considering I'm not planning to support rooms that big, it's a success.

I'm thinking to have "friendly-water" "friendly-air" ... and so on pathmaps for the other types of terrain.
Marking a tile (such as force arrows) not pathfindable is as easy as adding a tag to it.

I'm calculating valid tiles (obstacles/not obstacles) directly during the breadth-first search without performance issues. I could optimize this by calculating it once per turn, but it's not needed right now.

I've had some fun creating convoluted mazes where roaches pathfind to stalwarts (well, an even dumber version of stalwarts) and stalwarts pathfind to roaches at the same time. I find this behavior more interesting that the one present in DROD.

I've also kept the jump-point searching in the engine - it may be useful with certain kind of entities (Halph comes to mind), or when I will implement some sort of scripted NPCs (I'm planning to have a "pathfind to x,y" command).

I've done a lot of refactorings but I'm still unhappy with the code. I'm using lambda expressions pretty much everywhere. This makes the code easily readable but it's not helping with room serialization, since lambdas aren't serializable in C#. I will have to replace all of them, sadly, or find an alternative to serialization.

TFMurphy wrote:
And vittro, you really should make more of an effort to read through and figure out what the DROD source code is doing. Look up commands if you don't know what they do. Read through the comments in the code, compare what the code says to how things work in game. You're already familiar with programming itself, so this shouldn't be that alien to you.

I've been taking a look at the source code while developing my own engine. My approach is completely different from DROD's approach (I'm adopting a component-based entity system, for example) - but I've found useful code.

While I'm familiar with programming, I've started learning C++ seriously (got a book, doing exercises, etc) only a week ago. I've used managed languages my whole programming lifetime, mainly C#, some Java, some Javascript and some D.

I'm starting to get my head around C concepts like pointers, or C++ concepts like iterators, but they're still sort-of-alien to me (when I see the * and & operators I still have to stop and think about them for a minute).
When I look at the DROD source code it just screams "messy" to me. I'm sure, though, that it really isn't messy at all, I just have to get more used to the C++ syntax.



Ah well, back to refactoring.

____________________________
http://vittorioromeo.com

---

[Last edited by vittro at 06-14-2012 01:54 AM]

Red-XIII
Level: Smitemaster

Rank Points: 749
Registered: 08-05-2012
IP: Logged

Hello everyone, since I didn't understood very well the meaning of these two phrases about the source code of DroD I'd like to ask you something, Erik Hermansen wrote this:

"It is also wrong to reconstruct it using screenshots or other techniques, and that includes the media included in the free demo version"

"You just can't have all the media, i.e. the levels, in-game writing, graphics, music, sound effects, and voice samples"

Now, what "other techniques" and " in-game writing" stands for? I'm asking this because I wonder if with the source code of DroD I'd be able (actually my brother who is an informatic engineer since I suck in these things) to test some new features I thought a while ago. For exemple, is it possible to take the script of the adder and change it to create and try something new and show it here on the forum? Of course I won't distribuite it and it will remain strictly confidential and I'll delete it after it's done.
If "in-game writing" stands for this thing I just descrived then sorry, I won't touch anything.
Thanks.

____________________________
There's not some other world out there where everything's gonna be okay.
There's just this one, just this rock.
-33th Skywatcher

Moo
Level: Master Delver
Rank Points: 224
Registered: 10-14-2006
IP: Logged

In-game writing means just that; scrolls you see in the game for example. The restrictions are on the "content" of the game, rather than the code.

Red-XIII
Level: Smitemaster

Rank Points: 749
Registered: 08-05-2012
IP: Logged

Ok I got it, thanks.

____________________________
There's not some other world out there where everything's gonna be okay.
There's just this one, just this rock.
-33th Skywatcher

mrimer
Level: Legendary Smitemaster

Rank Points: 5411
Registered: 02-04-2003
IP: Logged

I've prepared and made the DROD 5.0 source code archive available for download (see first post).

____________________________
Gandalf? Yes... That's what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now at the turn of the tide.

robin
Level: Smitemaster

Rank Points: 856
Registered: 09-01-2004
IP: Logged

Downloading the source code seems to be buggy...
There won't start any downloading, I just go to a page with lots of "random" code

EDIT: seems to be an internet explorer bug, works fine in firefox

____________________________

---

[Last edited by robin at 02-18-2015 02:39 PM]

vittro
Level: Smiter

Rank Points: 489
Registered: 04-17-2005
IP: Logged

Necrobump.

Have you considered hosting DROD's source code on GitHub?

I use it for all my personal and private projects, and I'm convinced it is a great platform for open-source work.

The biggest benefit of having DROD's source on GitHub would be being able to easily browse/read the code from your browser, conveniently looking at the commit history. Another huge benefit would be being able to contribute through pull requests/issues.



____________________________
http://vittorioromeo.com

mrimer
Level: Legendary Smitemaster

Rank Points: 5411
Registered: 02-04-2003
IP: Logged

That's a great idea! We currently host our code on Bitbucket for internal team development. We'll consider opening this up in a way that would work for us and others.

____________________________
Gandalf? Yes... That's what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now at the turn of the tide.

---

[Last edited by mrimer at 03-09-2016 03:45 PM]

hyperme
Level: Smitemaster

Rank Points: 1428
Registered: 06-23-2006
IP: Logged

I've been poking around with compiling DROD for my own mysterious ends. Things have been progressing generally well with some help from skell, but I've hit one last problem.

It appears that drod_algorithm.hpp makes the compiler very unhappy - a few duplicate function definitions and what are apparently a big pile of syntax errors tend to do that, after all.

How would I fix/avoid this problem, and move one step close to a fully functional DROD?

____________________________
[Insert witty comment here]
Qzvlkx?

mrimer
Level: Legendary Smitemaster

Rank Points: 5411
Registered: 02-04-2003
IP: Logged

Hey, awesome! I hit the same issue on my build and skell wasn't able to help me sort it out on my end either. I'd say, to get it building, leave out that custom code (i.e., don't define the compiler token that includes those functions).

____________________________
Gandalf? Yes... That's what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now at the turn of the tide.

vittro
Level: Smiter

Rank Points: 489
Registered: 04-17-2005
IP: Logged

mrimer wrote:
That's a great idea! We currently host our code on Bitbucket for internal team development. We'll consider opening this up in a way that would work for us and others.

Hello Mike - hopefully I'm not being annoying - but I was really looking forward to this. Do you have any update on opening up the source code to an easily accessible platform like GitHub or Bitbucket?



____________________________
http://vittorioromeo.com

---

[Last edited by vittro at 12-31-2016 06:52 PM]

Banjooie
Level: Smitemaster

Rank Points: 1645
Registered: 12-12-2004
IP: Logged

vittro wrote: Do you have any update on opening up the source code to an easily accessible platform like GitHub or Bitbucket?

mrimer wrote: We currently host our code on Bitbucket

.... ...?

skell
Level: Legendary Smitemaster

Rank Points: 3824
Registered: 12-28-2004
IP: Logged

The code is hosted in a private repository and it can't be made public because the non-open source part of the code is in the same repository. So it's a bit of work to fix that. Which is why it is not done super easily. Which is why Vittro's question makes sense.

____________________________
My website

G Eye
Level: Goblin
Rank Points: 21
Registered: 01-23-2012
IP: Logged

Which language does this game use?

C#?
C++?

____________________________
Respire

IQubic
Level: Delver

Rank Points: 97
Registered: 11-22-2015
IP: Logged

G Eye wrote:
Which language does this game use?

C#?
C++?

It uses C++. Don't expect it to be simple to compile, though, as you need several 3rd party libs to be present and linked correctly.

I tried for a few days, and then gave up due to the difficulty. of compiling DROD.

____________________________
Trans Woman (She/Her Pronouns)
121st Skywatcher

uncopy2002
Level: Smiter
Rank Points: 432
Registered: 07-28-2014
IP: Logged

Compiling DROD is like a journey. You don't simply git clone and run MAKEFILE (or something like that) and see magic unfold and your DROD is served. Only after hours and hours of pain you will reach the end, and get the satisfaction out of it.

Joking aside, I recall there's a text file somewhere which comprehensively documented the last brave adventurer's attempt to compile DROD. I can't seem to find it again though. Maybe somebody else can recall where it's at.

IQubic
Level: Delver

Rank Points: 97
Registered: 11-22-2015
IP: Logged

uncopy2002 wrote:
Compiling DROD is like a journey. You don't simply git clone and run MAKEFILE (or something like that) and see magic unfold and your DROD is served. Only after hours and hours of pain you will reach the end, and get the satisfaction out of it.

Joking aside, I recall there's a text file somewhere which comprehensively documented the last brave adventurer's attempt to compile DROD. I can't seem to find it again though. Maybe somebody else can recall where it's at.

Download the latest source code .rar, and open it up. Inside is a file called CompilingDROD.txt

____________________________
Trans Woman (She/Her Pronouns)
121st Skywatcher

IQubic
Level: Delver

Rank Points: 97
Registered: 11-22-2015
IP: Logged

I have successfully compiled DROD on Linux. If anyone wants to know what I did, I'd be more than happy to write a guide. However, said guide would only apply to people running Linux.

NOTE: since not many DRODers run Linux, I'll only write the guide if specifically asked.

____________________________
Trans Woman (She/Her Pronouns)
121st Skywatcher

---

[Last edited by IQubic at 02-16-2017 05:06 PM]

mrimer
Level: Legendary Smitemaster

Rank Points: 5411
Registered: 02-04-2003
IP: Logged

The DROD and DROD RPG source code is now* officially available on GitHub:

https://github.com/CaravelGames/drod

There are multiple outstanding PRs that I'd like to review, so they can be merged and get into future official releases at long last.

New PRs are welcome!


* For those not aware, there's a backstory to this. If you're interested, here it is, in abbreviated form.

I took an extended hiatus from DROD development. A few years back, skell published the DROD source code on github through his organization. He put together an excellent script to make building the required third-party libraries easy and included it with directions in the repo.

This weekend, I showed up to dabble in making some minor fixes and improvements, which the community has been more than patient in waiting for. The first thing I noticed is that bitbucket had jettisoned all the official Caravel Hg-based repos. (Gasp!)

So, not being one to waste a good crisis, I got with skell and schik and we agreed to transition the current github repo over to a new CaravelGames org. Standing on the shoulders of giants, I got up and running on a fresh development PC.
Thanks to skell's script, I was able to get both DROD and DROD RPG up and running with a relative minimum of pain. Major props to skell for automating this endeavor! Now, the "journey" feels more like taking the RCS to Rooted Hold.

I've added VS2019 project file support and brushed a couple cobwebs out of the code to address some newer compiler warnings.

I had a local copy of the code, so I was able to also add the DROD RPG source, which I placed in the same repo under a 'drodrpg' sub-directory. Added VS2019 project files there too and got those working under this new structure.

Needed to upgrade SDL2 to 2.0.12 to skirt around a Windows compiler bug I was seeing on Windows 10 with VS2019 and SDL 2.0.5.

And the games just run. It's like magic.

Now I can crack my knuckles and get to the real work! For anyone (still) interested in collaborating on fixes, improvements, etc., please jump right on in and ask any questions you may have.

____________________________
Gandalf? Yes... That's what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now at the turn of the tide.

---

[Last edited by mrimer at 09-21-2020 08:24 PM]

disoriented
Level: Smitemaster

Rank Points: 2495
Registered: 08-07-2007
IP: Logged

Congratulations! I don't really know what this means exactly, but it sounds like the source code is now in an easier-to-maintain format for everyone.

I see there are Windows, Linux, and Mac build instructions.

Will this make it easier to keep builds for the different platforms in sync?
Will this make it quicker to get bug fixes into the source, and subsequently get releases out the door quickly?
Will this make it easier to create builds for new processor architectures (e.g. Mac-ARM?)


____________________________
34th Skywatcher

Best to PM me, since I might miss your message on CaravelNet chat.