Where to start in the code?

[nightblade]

Background: I've played FFXI since it was released on PC and taken a few breaks because of work. Saw this project was available after seeing a video related to resurrecting dead game servers [and I know FFXI server are still active.] through reversing. As I like FFXI a lot and would like to play on a local server/public server years down the road when SE servers are nonexistent; this project piqued my interests. I've got quite a few years experience programming so I feel I can contribute some while I work on my server.

I'm still working on getting down the structure of the code [since I downloaded the code and setup a server a few days ago.] from reading the src directory. I can wait for patches to quests, mission, and other this aside for now from other developers since I think it be more fun for me to work on the underlying server code.

My problem lies in that the newest git repository still doesn't have a working monster movement system. My mobs spawn and sit, maybe turn around, or pretend to take a step and stop. With the spawn point placement this makes it easy to isolate monsters for solo play, but lacks a bit of the thrill of making sure you're distanced from sight links. So I'd like to patch the monster movement on my server for my first project; if there isn't already a working patch available.

I've searched Google and found a few discussions related to the problem [a bit dated] relating to lack of navmesh data and code. Is the navmesh still a problem for areas or has it already been committed? I found the code for CPathFind::RoamAround() in ~/src/map/ai/helpers/pathfind.cpp; under the guidance from the development team I ask, Is this the most appropriate place to place any modification to the monster movement [roaming] behavior, or are there additional places to take note?

I also checked out the 'wanted pages' page, but there all red linked. Are there any other behaviors that could be implemented that would be of interest? Early [game] missing behaviors are welcome that you know about that are lying on the table under other notes.

Note after server setup. The conquest system was whacked; in that all regions were beastmen owned except Ronfaure [Windurst], Zulkeim [Windurst]. I wrote a SQL script to fix this with a fresh start server feel in mind for the levels of influence. It is all documented in the script in addition to the missing wiki region_id information reference. That being said I had no clue what the maximum total influence could be between all cities and beastmen, and the values that were added with the download had beastmen with 9700; so I took a guess and set all regions with a combined total of 1000 points thinking that 10000 might be a cap for any one influence. I'll share this with my first post!

Regards,
nightblade DSP

[kjLotus]

the main issue with navmesh (i think) right now is that the zone meshes aren't readily available, nor are they optimized for pathfinding. the original author of those left some time ago and nobody has touched it since then (not really a huge priority). yes, ai/helpers/pathfind would have everything related to mobs moving

for other missing things off the top of my head, crafting guilds need all the guild point related systems working is one of them. a lot of BCNMs aren't implemented for another (mostly just the ones that were done for gil).. i'm sure there are other things people can think of if you came in irc and asked some of the server admins

for conquest, i put those as the default values on purpose: get out there and conquer the beastmen! (i still have a bit of work to do on conquest in the near future..)

[atom0s]

The navigation mesh implementation was done by lautan who started it then disappeared. The intent was to get the community to work on the meshes for each zone with some help from RZN (from FFEvo) as RZN made a library to dump the maps mesh data from the map .DAT files. The only mesh that was made so far was for West Ronfaure as a test / example. However, the mesh alone is 4MB on disk. Which would mean that if all meshes took 4MB of data there is at least 1-1.5gigs of RAM needed just to load the data let alone use it. (This, assuming that the implementation remains the same and loads the full mesh into memory vs. querying routes at runtime or similar.)

If you are interested in looking into the mesh information / data you can check out RZN's lib here: (The lib cannot open any newer zones from Adoulin. (Not that we are anywhere close to working on that content anyway.))
http://www.ffevo.net/files/file/236-ffxi-map-lib/

The current mesh that was modified and loaded for West Ron is located in:
/darkstar/scripts/zones/West_Ronfaure/NavMesh.nav

To help you get into the source a bit more, here are some important things to note:
- /src/common holds source files that are used across all 3 servers. (With the exception of detour and recast.)
- /src/login is the source code to the lobby server.
- /src/map is the source code to the game server.
- /src/search is the source code to the search server.
- /src/map/packet_system.cpp is where you can find all the client -> server packet handlers.
- /src/map/packets/ is where you will find all the packets that are sent from the server to the client.

DarkStar is HEAVILY based on the rAthena MMORPG server found here:
https://github.com/rathena/rathena

You'll see a lot of files from there within our project.
The person that took the ProjectXI code base and reworked it used rAthena as a starting point on where to go / work from for a more stable server.

As for things to work on that are not currently done:
- BCNM's (As kjLotus said, a lot of them are missing.)
- Conquest (Does not really work well at all, but kj has mentioned he plans to tackle that.)
- Dynamis (Implemented but done in a very poor manner, has lots of issues, does not work like retail, etc.)
- Fishing (Myself and Setzor have been working on this recently, we have fishing fully working, just working on some last tid-bits. [Not commited to main repo yet.])
- Jobs (BLU, PUP, COR, SCH, DNC all need work.)
- Limbus (Needs a lot of work since it is not really implemented 100%.)
- Quests (Random quests throughout the world.)
- Sea (Pretty much nothing is done in sea.)
- Teleport Crystals (Homepoints within each town / zone are not implemented.)
- Various town NPCs with specific purposes. (Weather system, Map vendors, etc.)

Are some things I can think of off the top of my head.

[nightblade]

kjLotus and atom0s, Thanks for the information and the forward links to the map data; this will help out a great deal.

That is interesting to note about the navmesh data size and what it may mean in the long term server requirement. I'll see if there is anything I can do to bring it down when I work on the code. So far i've just been experimenting with the following bits of navigational consideration from my experience with FFXI. If anyone has more true data could you please forward it my way?

Consideration [Roaming]:
1. Monsters don't travel terribly far from their original spawn point less any aggression [Previously they would walk back to their spawn, but now they depop and respawn],
1.a (Assumption) There must be a statically set maximum roaming distance for all monsters. This could be anywhere from 23.0f - 60.0f or more, but from my experience monsters will tend to turn around and navigate within a cylindrical field around their spawn point roughly < 30.0f.
1.b The chance to turn around [or rather choose another direction] mid movement should be evaluated.
1.c Monster hit an obstruction [Wall, Tree, Large Rock] choose new direction and continue, or stop.

Thanks for the information again. I'll keep ya posted on any successes.

Regards,
nightblade DSP

[whasf]

Come hang out in IRC (rizon, #darkstarproject), we're usually there..

[atom0s]

I think that the game handles navigation in three separate methods for monsters as movement is different based on what is happening with the monster:

A. Monster Is Roaming
When monsters are roaming on retail, it appears they use a point-to-point connection route to follow that is picked randomly. I do not feel this route is generated on the go as they walk, but rather once. The path, in my opinion, is given a start point and branches from that, randomly, a random amount of points up to a certain distance away. So in turn this is how I suspect that works:
(Pseudo Code):

Code: Select all

void CBaseEntity::BuildRandomNavigationPath(std::vector<Point>& points)
{
    // Obtain a random number of points to walk.
    //
    // The rate of long range walks should be handled in some manner, such
    // as limiting the random to a percent change of being higher then a
    // certain number etc. Most roams on retail seem to be short distance
    // suggesting that the roam generation is clamped low and limited.
    auto MAX_WALK_POINTS = rand() % 25;
    
    // Obtain the closest point on the navmesh we are currently at.
    auto closestPoint = this->loc.zone->m_navMesh->closestPoint(this->loc);
    
    // Next, walk each point finding random points connecting to the previous.
    while (MAX_WALK_POINTS > 0)
    {
        // Effectively, FindRandomPoint can walk a max of 'MAX_ROAM_DISTANCE' points to let
        // the monster roam further then just 25 single steps in the nav mesh.
        auto nextPoint = this->loc.zone->m_navMesh->FindRandomPoint(closestPoint, MAX_ROAM_DISTANCE);

        points->push_back(nextPoint);        
        MAX_WALK_POINTS--;
    }
}

This would allow the mob to roam like retail mobs do where they have the random stutters, turn arounds and so on that look wtf at times.

Of course this would be something that can be cancelled mid path if the monster is aggro'd or interacted with in some other manner.

B. Monster Is Following / Aggroing
When the monsters on retail are in an aggressive state, their navigation pathing is completely different. Instead of walking a random path they are calculating the closest path to reach the target. I would assume this path is recalculated every tick, or every other tick. They do not walk a random path to the player, but instead the 'best suitable path' to the player. In some cases, I think SE's coding shines true here where you will see monsters take some retarded routes to get to the player instead of the shortest. Some times going around an obstacle they did not need to etc. I don't feel this is on purpose, but rather just poor implementation of navigation on SE's part.

At this point, I think something like A* pathing would work best to find that path to the target fast and effectively.

C. Monster Is Scripted Path
For this the path is predetermined for the monster to roam on. For this it would be as simple as walking the path constantly, refinding the closest point if the entity is interacted with during the walk.


This is just my speculation based on how things look on retail.

[whasf]

I think the way the navmesh works now is they can roam "randomly" within a certain radius from their spawn point?

[fnx]

Working on meshes had piqued my interests. I have a little programming background and would be interested on cutting the meshes down to save space, flatten out and remove the obstacles/non navigable terrain perhaps.... Can anyone point me in the right direction for mesh editing? I would love to start on a small zone as a proof of concept.

[whasf]

Working on meshes had piqued my interests. I have a little programming background and would be interested on cutting the meshes down to save space, flatten out and remove the obstacles/non navigable terrain perhaps.... Can anyone point me in the right direction for mesh editing? I would love to start on a small zone as a proof of concept.

See this thread: viewtopic.php?f=20&t=1276