Monsters AI (sandbox)

I was thinking... How to make monster not start flying or go through a montain, or wall?

I mean, we need XYZ of the map to make the scripts so mob can walk in the map, and not stay still. But, what happened, if you enter a vision range of a X mob. Lets assume you are in a flat ground. Then, you enter in a valley. If you dont do something, the mob will start "fyling" over your head. So, how its supposed to work? Get the actual player XYZ and create a formula to generate the XYZ coordinates the MOB needs to follow to reach that player?
Even if you dont enter a monster vision range.it'll still be walking on the map right? What we should do for the mob to always stays in Garden of Freedom for instance, not suddenly enter the XYZ of Ricarten... I'm assuming that our current server.exe reads all the smd file seeking for the XYZ of the map.But thats still strange..how would the server know if theres a wall,or a mountain, or a lake that the mob cant walk there... Do u understand the point I'm trying to make here? I think this'll be the hardest part to me.. I need someone who knows, just a little bit, of how this system works..

my plan for that was to use mini-maps to build a detailed height-map matrix instead of process all the ase files.

So all the objects on the map will be obstacles with a big height to force mobs not pass to there, and to obtain the relative Y position (height) of the terrain, work with the grey-scale of the map. Although as far i remember if not touch the Y position on movement, then the client will handle it for you.

So then will have 2 main objects, the array Map(x,z) (2d sized) to handle all the objects and the size of each object and array HeightMap(x,z) with the Y as result to handle the vertical position.

So with this model will lose any kind of physics 3d engine calculation (collisions, torques, momentums) and will simplify the calculations as if we were just moving boxes :p, but this game not requires really the precision of very complex stuff.
So this model will be good enough and client will be leave to handle mostly all the animations. So just need to keep to have a separated timeframe counter to sent the proper animation cycle to initiate the movements.

All stage SMD files have a precomputed (at .ase->.smd compile time) fixed-size block with data that is used for this purpose of knowing where a monster/npc can walk. It also contains pointers to the vertex/face blocks etc that's in the rest of the SMD file.

This block starts at offset 0x22C and it's size is 0x40074.

I can't help you on the format of the contents of this block though, but I can tell you that's where you need to look at.

You'll also notice my SMD reader ignores this block as it is not needed for the purpose of retrieving the original .ASE contents. It is however very much required by both the client and the server.

---------- Post added at 03:59 PM ---------- Previous post was at 03:51 PM ----------

Oh I do have some more info. The data block is actually a class thats saved in all SMD's, I call it the 'Stage' class, and this is it's definition as I have it at the moment ;)

Code:

---

class Stage
{
private:
#ifdef _GAME
        static const DWORD          pfnGetHighestPoint        = 0x00463C30;
        //00463C70 = Is Position IN map
#else
        static const DWORD          pfnGetHighestPoint        = 0x004694D0;
#endif
public:
                                                  Stage();
                                                ~Stage();

        BOOL                                  bState;

        char                                  szPadding[0x40060];

        int                                  iWest;
        int                                  iSouth;
        int                                  iEast;
        int                                  iNorth;

        int                                          GetHighestPoint( int x, int y );
}; //Size = 0x40074

---

Thnx for share it sandurr, this is very usefull knowledge.

that block starting in 0x22C doesnt even seem like XYZ values. I bet they are encrypted too, no clue of HOW to use that values or even how to DECRYPT them. I'm not so good with math... indeed I hate it. If someone can help me, or point me where server or client decrypts that block of code I could decrypt them too.

Actually I just reminded myself that the Stage does contain pointers to the Vertex/Face/all other blocks of the Stage, so it might be that the AI uses that info server side aswell, although I'm not sure yet and not going to look at that now.

Here's a little more expanded Stage class, there's alot more unexplained methods though that are not in here.

Code:

---

class Stage
{
private:
#ifdef _GAME
        IMPFNC pfnConstructor                = 0x00462BE0;
        IMPFNC pfnDestructor                = 0x004655C0;
        IMPFNC pfnGetHighestPoint        = 0x00463C30;
        IMPFNC pfnSaveToFile                = 0x004648C0;
        IMPFNC pfnLoadFromFile                = 0x00464A80;
#else
        IMPFNC pfnConstructor                = 0x00468480;
        IMPFNC pfnDestructor                = 0x0046AF50;
        IMPFNC pfnGetHighestPoint        = 0x004694D0;
        IMPFNC pfnSaveToFile                = 0x0046A160;
        IMPFNC pfnLoadFromFile                = 0x0046A320;
#endif

public:
        //Attributes
        BOOL                                  bState;                                //TRUE if Stage is Loaded, otherwise FALSE

        char                                  szPadding[0x40060];

        int                                          iWest;
        int                                          iSouth;
        int                                          iEast;
        int                                          iNorth;
       
        //Operations
                                                  Stage();
                                                ~Stage();

        /**
        * Retrieves the highest 3D Y value in the Stage at the provided 2D coordinate
        * @param iX the 2D X coordinate
        * @param iZ the 2D Y coordinate
        * @return int the highest 3D Y value at the provided 2D coordinate
        */
        int                                          GetHighestPoint( int iX, int iZ );

        /**
        * Saves Stage to File
        * @param pszFilePath the File Path to Save the Stage
        * @return TRUE if saved
        */
        BOOL                                  SaveToFile( const char * pszFilePath );
       
        /**
        * Loads Stage from File
        * @param pszFilePath the File Path to Load the Stage from
        * @return TRUE if loaded
        */
        BOOL                                  LoadFromFile( const char * pszFilePath );
}; //Size = 0x40074

---

Quote:

---

Originally Posted by SheenBR

that block starting in 0x22C doesnt even seem like XYZ values.

---

As I understand it (ie. not very well, because this is the 3D that creeps into programming which I can't "visualise" let alone program around) XYZ is okay for points (location) but useless for planes and paths... what you need is 3D Vectors.

I could never work out how to convert between the two, but your path should be one "vector" (this I can visualise in 2D) and the ground is one or more "planes" from which you can tell if your path crosses any plane, or calculate the place at which a path intersects a plane.

For example, you can create a 2D path from an XYZ to it's lowest point... (absolute zero) and the point at which that path intersects the plane is the ground level... that's how you work out where an NPC or monster spawn appears on the map from the point recorded in the SPM file... even if that point is actually in the air.

The same calculation can be used for each update for monster movement to stop them "flying" or "sinking in quicksand" when moving along a slope... except when the ground has multiple heights... which is why the monster should move along another "path" calculated to travel between one intersection and another at all times.

This is also why "height map" will not work for PT. (at least, not always) Some 3D games, this is fine... for example, that was how Doom worked. But PT can, and just once or twice does implement bridges. These cannot be represented by a single height map, as there are at least two valid ground points for a single X, Y location. :wink:
http://i.imgur.com/PnEEi.png

This is a good, free, open source path finding engine which should allow you to abstract your self from the nitty gritty. (used in the Open Source WoW server engine MANGOS)

Here are some funny examples of messed up 3D pathing in modern games:-
Pathfinding Bugs in Modern Games
Expect to see lots of that, and more while debugging your AI. :lol:

--- EDIT ---

Oh yes... you mentioned crossing map boundaries. The AI must consider the map edge as an invisible wall. It must also have an implementation for "destination unreachable". That decision choice will be essential for many reasons, not just to stop monsters following you across maps. For example, if you have jumped / fallen into a building which the monster can see you (close enough) but cannot climb the walls which surround you... or you are on a steep spire which the monster cannot climb up, but you can climb down.

If it cannot conclude it can't reach you, it may continue to try to calculate an impossible destination indefinitely and lock up you server. (or, at least one of it's threads)

omg, this seems hard, I dont know anything about 3D...

I would probably begin by implementing A* (A-Star) 2D algorithem + XYZ against height map with current height - new height not less than X or greater than Y, for "walls" to begin with... then experiment with replacing it with a path finding engine which I could "plug-in" without understanding how it worked too deeply. XD

Good luck to you though. :D:

Yeah 3d computing is a pain, but thats why i though on use a simpler model and just "forbid" the monsters go into difficult areas, just whatever will trouble ur simple calculations would become an invisible obstacle, Simple and plain. Yeah is a low & dirty trick but it will works, but you are the designer of the AI on this case and u can choose not be so troublesome by very hard task. A simple AI will be more than enough for many of the maps.

edit:
i doubt your AI will need to have tactician mobs that climbs walls & ambush players and that keeps healing their ally monsters :p.

You will need simple walk to destiny points, follow target logic and round around the obstacles maze.

lol, I dont want any super special master AI... The problem is I dont even know how to "create an AI"... I tried to search some examples but no results. Or they are too complicated or its in another language. What I would like to see is a mob AI already working so I can see what its being done and then adapt it to my needs.

Look this A* Pathfinding for Beginners

yes, but I would need to get the coordinates of the map... something that I dont know how to read them from the smd file. I didnt understand that offset sandurr gave to me.

Ok dont worry for that yet, do something easier... walk around in a map with admin console and write the coordinates of the boundary limits of it, and the coordinates of any obstacle on that map. Then you have a basic map :p.


Edit:
Dont worry much by vertical coordinate (y) because as far i remember if you dont specify it on the movement packet the client automatically calculates it over the terrain.

well, at least I have to know how to spawn monsters, which I cant understand how it works from even that VB source or that one in Java =p

But I'll try what you said.

So, Y isnt important? only X and Z right?