Player Pathing

[doggan]

Hey all -

I just heard about Freeablo a couple days ago. I love the idea for the project. Drag and drop your MPQ, and voilà - you can play the original Diablo cross-platform. Also the future plans of turning it into a general purpose engine with mod development + scripting is really intriguing. Obviously, lots of work left to do, but still exciting.

I spent a little time hacking around with the existing code to see what I can do (thanks for accepting my pull requests!).

Today I was planning on looking into the "NPCs and living monsters shouldn't be passable" issue for the current milestone, but got a little sidetracked and ended up trying to improve player movement. Currently the player moves in straight lines, so when collision is enabled you get stuck on corners and it's difficult to move.

Here's a short video of the progress: video link

The player doesn't move yet, but you can see the path that the player will take.

As a side note, I ended up writing a general purpose A* algorithm and some debug display utilities. Hopefully these will prove useful in other systems too!

That's all for now. I look forward to contributing more to this project!

[Necrolis]

Looking good! seeing as you made a topic, I'm gonna hijack it a little

I was actually thinking about the best way to do the collision related things over the past day or two, and the path finding is going to need to tie into it, seeing as currently collision data is only available for the level's "geometry" (via the underlying tileset flag), kinda decided the best approach was to assign each tile 8 bits in a 2D array, where the lower 4 bits are terrain style flags such as block_ground, block_air, block_disjoint(in the case of teleporting), block_missile (for things like walls made of bars and certain doors); and the upper 4 are unit flags that determine dynamically shifting data (aka, one bit for monsters, objects, items and players). kinda want to put that out there and get some feedback (are we ever going to need anything more than 2D collisions? what sort of interactions are to be supported? whats needed for pathing etc.).

Another alternative to consider is using a quad-tree to hold all the unit data, and assigning some for of 2D OBB/AABB/Sphere to check collisions against, but then we get into the awkward situation of having to check two different places for collisions, however the quad tree does make other takes easier, and make be useful later one to aid in things like on-the-fly terrain loads, generation and stitching.

As a side note, I ended up writing a general purpose A* algorithm and some debug display utilities. Hopefully these will prove useful in other systems too!

moar debugging utilites are never bad! we'd need this to debug monster & missile pathing as well.

[wheybags]

Wow, that looks amazing!
Necrolis: I don't think we'll need more than 2d collisions (at least, I can't see how we would).
Also, the bitfield approach you described does sort of exist already in the SOL files, but the only field we are reading currently is the passable flag. There's a bunch of other stufff in there apparently but I haven't looked into it.
I had planned to move actor data into a big 2d array, so collision code could just check for the presence of an actor at that index in the array.

[Necrolis]

Necrolis: I don't think we'll need more than 2d collisions (at least, I can't see how we would).
Also, the bitfield approach you described does sort of exist already in the SOL files, but the only field we are reading currently is the passable flag. There's a bunch of other stufff in there apparently but I haven't looked into it.

Yeah I saw as much, not sure what other flags the SOL files hold (will do some checking), but it may be better to plan for certain future things now. As for the "more than 2D", I mean things like pseudo-z (generally missiles that travel as parabolic arc's etc).

I had planned to move actor data into a big 2d array, so collision code could just check for the presence of an actor at that index in the array.

hmmm, sounds like you want a 2D array of chained pointers, which might get a little compilcated seeing as not everything is the same size. I'll also just leave this here as well, might be useful: http://cg.informatik.uni-freiburg.de/co ... _08_sp.pdf

OP: Spam bots? that means you've hit the big time

[wheybags]

ugh spambots ;_;
Deleted em all for now, will have a look into hardening against them

[doggan]

Necrolis: I don't think we'll need more than 2d collisions (at least, I can't see how we would).
Also, the bitfield approach you described does sort of exist already in the SOL files, but the only field we are reading currently is the passable flag. There's a bunch of other stufff in there apparently but I haven't looked into it.

Yeah I saw as much, not sure what other flags the SOL files hold (will do some checking), but it may be better to plan for certain future things now. As for the "more than 2D", I mean things like pseudo-z (generally missiles that travel as parabolic arc's etc).

Pseudo-z can easily be done with a bitfield approach too. For example, 0x1 is full collision so no objects can pass through. 0x2 is low obstacle so projectiles can travel over. 0x4 is a high obstacle that can be slid under. Etc. A user application (or mod) would be able to define as many heights or types of collisions that it wants to

I had planned to move actor data into a big 2d array, so collision code could just check for the presence of an actor at that index in the array.

That works, but IMO it's not very flexible, since only actors can affect collisions. Also not very cache-friendly, since you need to query other actors for collision info (probably not a big deal on PCs, but always something good to keep in mind).

The way I did it on a previous project was to use the level bitfield with 1 bit for dynamic collisions. The bitfield itself is a single chunk of memory that is quickly hashable via x/y coordinates. At the beginning of the frame, you zero the dynamic collision bit for all tiles. After this, all your actors and game objects do their pre-updating. Each actor hashes their current position and sets the dynamic collision bit for their tile (you can even set the bit atomically if your actors are running in parallel). Now the bitfield is fully updated for this frame, so all actors can run their update and read collision info in constant time.

Of course there are other approaches, but the good thing about this one is that it decouples your game objects from your collision data. Anyone (even a modder via script) is free to affect the collision info. Closed doors, fat units that take up more than one tile, etc... can block off as much area as they need.

[wheybags]

That works, but IMO it's not very flexible, since only actors can affect collisions. Also not very cache-friendly, since you need to query other actors for collision info (probably not a big deal on PCs, but always something good to keep in mind).

I meant a 2d array of pointers, so you could just check if it's null or not without having to go reading from all over the place.
It already kinda does this for passing actors into the renderer, would make that easier if it was just copying from one 2d array into another, where as for now the actors are just stored as a big vector of pointers in the game thread.
Ultimately, I think either approach would work fine, so I guess it's down to the personal preference of whoever ends up implementing it :p

[Zilla]

Hi there,

What is the current status of this path finding implementation?
I just learnt about this project a few days ago, and I started my own A* implementation, before checking the forums and seeing that there was already work ongoing on it.

I also notice that this post is over a year old, so I was curious as to what happened with this effort

[doggan]

I also notice that this post is over a year old, so I was curious as to what happened with this effort

After the original video that I posted above, I didn't pursue it much further. My day job was using C++, so I kind of lost interest in this project as I didn't want to do the same thing for my hobby I ended up creating a spin-off of this project in node.js for the browser (https://github.com/doggan/diablogl). Player pathfinding is implemented there, so feel free to check out the code.

Also, here is the A* I wrote for originally plugging into freeablo. Maybe it can help you out:
https://github.com/doggan/code-dump/tre ... tar_search

Cheers!

[wheybags]

Aww, don't splinter the effort! :p
Better to have one working project than two broken ones.
And if you REALLY MUST run diablo in a web browser, well, there's always emscripten...