;D

More Steps Towards Perfect Mapping For Bots - D2
[hr]

I created this thread in the hope of opening the conversation on Mapping Concepts for Diablo II.  Personally, I am to create a bot that can move around on a map with the same knowledge present in a real player.  I want the bot to track the movement/location of all Objects/Units and the walking cells of the map.  It is my hopes that any information tossed in here might help contribute towards different working map techniques helping us to create our own, more complex, bots.

I am fairly novice so don't expect a lot from reading my blurb below, but hopefully someone finds the information useful in someway.



Mapping Concepts:

Generally speaking, there are two main concepts for laying out a map for your bot.  Objects, or Map Data.  Using either of these techniques, your bot will react to the position of different obstacles and manuver its way towards your desired goal.



Objects:

For Objects, you simply have your Bot react to the location of certain objects in view.  For instance Standard1 and Standard2 in Act1. 

These objects will come into view using packet 0x51 posted previously by Ringo

[code]0x51
D2GS_OBJECTASIGNMENT
Lengh = 14

51 02 XX XX XX XX 25 00 59 16 A0 15 02 00
(BYTE) Object Type
(DWORD) Object ID
(WORD) Object Unique Code
(WORD) Location X
(WORD) Location Y
(BYTE) Objects State (0x00=no &HE will follow, 0x02=expect a &HE)
(BYTE) Interaction Conditions
[/code]

The object's ID (35 or 36 in the case of Standard1 & Standard2) will match the Object Unique Code in this packet.

Bot Note:  It is always a good idea to seperate NPC/Monster/Summon/Merc/Player and Object types into seperate arrays to help with debugging your bot.  It also makes your own home-made minimap a little easier to use custom colours!

One importent decision to make is weither or not to work with object sizes.  I'm sure you've noticed during your playing that object sizes very, a lot.  And the location of the objects listed by 0x51 is not always entirely accurate. 

If you choose to ignore object sizes, make sure you set your bot to stay a set distance away from all objects.  This helps prevent your character from "sticking" to objects and being unable to walk past them.  The best idea using this method, is simply to scroll through the object list and look for the maximum object size out of all objects.  This should keep you relatively clear from object obsticles, but will reduce your pathing size.

If you use object sizes, keep the sizes and offsets listed in mind! 

Example: 
Your object might be size 10x10, at location 100,100. 
If the offset is 0, you can walk past the object fairly easily from 90,90 to 110,90. 
But if the objects offset is at -10, -10, remember your object Actually Exists at 90,90. 
And in that case, you might not be able to walk past it!



Map Information

To gather map information can be a little difficult. 

Packet0x07

One technique is to listen to the packet 0x07 for Area and Floor Information details.  Maybe someone can post more information on here about that technique?  I am currently working on using the 0x07 packet to determine the map information, but have no complete information to post on this.  I know it is made up of the 2 Words and 1 Byte (AreaID) but this packet changes format under certain circumstances.  I have tested this fairly well and determined on my own that it is indeed 2 Words and not 4 seperate bytes.

ReadProcessMemory/Use D2 Functions

Another technique is to simply emulate a Map Hack (such as Stings / Mousepads maphack) and to load this information into memory or a datafile instead of the minimap.  This is probably one of the best ways to do this, but is mostly for good C++ programmers.  I'm sure most people will tell you, playing with D2's functions by inserting dll's is very risky.  And loading any application as a .dll has the potential to be detected.  Its just my opinion but this can be one of the highest risks for getting banned for novice hackers looking to recreate the maps in D2.

On that account, a player can also ReadProcessMemory of Diablo 2 to grab the map information.

Origionally Posted by Myhrginoc on Phrozenkeep

Myhrginoc was able to gather some information on mapping that might be useful to C+ programmers
[code]Code:6FD77190  /$  SUB ESP,438
6FD77196  |.  PUSH EBX
6FD77197  |.  MOV EBX,ECX                         
6FD77199  |.  PUSH EBP
6FD7719A  |.  PUSH ESI
6FD7719B  |.  MOV EAX,DWORD PTR DS:[EBX+20]
6FD7719E  |.  MOV ECX,DWORD PTR DS:[EBX]         
6FD771A0  |.  XOR EDX,EDX
6FD771A2  |.  PUSH EDI
6FD771A3  |.  MOV ESI,DWORD PTR DS:[EAX+8]        ;  "ptGetPreset"
6FD771A6  |.  MOV ECX,DWORD PTR DS:[ECX]
6FD771A8  |.  MOV EAX,DWORD PTR DS:[ESI+C]
6FD771AB  |.  MOV DWORD PTR SS:[ESP+30],EBX
6FD771AF  |.  MOV EDI,DWORD PTR DS:[ECX+4]
6FD771B2  |.  LEA EBP,DWORD PTR DS:[ESI+C]
6FD771B5  |.  CMP EAX,EDX
6FD771B7  |.  JNZ SHORT D2Common.6FD771E6
6FD771B9  |.  MOV EAX,DWORD PTR DS:[ESI+4]
6FD771BC  |.  LEA EAX,DWORD PTR DS:[EAX+EAX*2]
6FD771BF  |.  LEA EDX,DWORD PTR DS:[EAX+EAX*4]    ;  15 * [ESI+4]
6FD771C2  |.  MOV EAX,DWORD PTR DS:[ESI+8]        ;  ptr to LvlPrest.bin record
6FD771C5  |.  LEA EDX,DWORD PTR DS:[EAX+EDX*4+44] ;  get the name string for the file
6FD771C9  |.  PUSH EDX
6FD771CA  |.  MOV EDX,DWORD PTR DS:[ECX+8]
6FD771CD  |.  MOV ECX,EBP
6FD771CF  |.  CALL D2Common.6FD76AD0              ;  ds1 loader is down in here
[/code]
[quote]

[code]Code:6FD771BF  |.  LEA EDX,DWORD PTR DS:[EAX+EAX*4]    ;  15 * [ESI+4][/code]

[ESI+4] is the File Column Index in LvlPrest.txt (0 to 5 means column File1 to File6)
15 is the width of the string in the .bin for each File columns


Stack build that defines LvlPrest.bin, now you can see where the data is in the record:

[code]
Code:0012ECB0   6FDC970C  ASCII "Def"
0012ECB4   00000002
0012ECB8   00000000
0012ECBC   00000000
0012ECC0   00000000
0012ECC4   6FDC9704  ASCII "LevelId"
0012ECC8   00000002
0012ECCC   00000000
0012ECD0   00000004
0012ECD4   00000000
0012ECD8   6FDC96F8  ASCII "Populate"
0012ECDC   00000002
0012ECE0   00000000
0012ECE4   00000008
0012ECE8   00000000
0012ECEC   6FDC96EC  ASCII "Logicals"
0012ECF0   00000002
0012ECF4   00000000
0012ECF8   0000000C
0012ECFC   00000000
0012ED00   6FDC96E0  ASCII "Outdoors"
0012ED04   00000002
0012ED08   00000000
0012ED0C   00000010
0012ED10   00000000
0012ED14   6FDC96D8  ASCII "Animate"
0012ED18   00000002
0012ED1C   00000000
0012ED20   00000014
0012ED24   00000000
0012ED28   6FDC96CC  ASCII "KillEdge"
0012ED2C   00000002
0012ED30   00000000
0012ED34   00000018
0012ED38   00000000
0012ED3C   6FDC96C0  ASCII "FillBlanks"
0012ED40   00000002
0012ED44   00000000
0012ED48   0000001C
0012ED4C   00000000
0012ED50   6FDC94E4  ASCII "SizeX"
0012ED54   00000002
0012ED58   00000000
0012ED5C   00000028
0012ED60   00000000
0012ED64   6FDC94DC  ASCII "SizeY"
0012ED68   00000002
0012ED6C   00000000
0012ED70   0000002C
0012ED74   00000000
0012ED78   6FDC96B8  ASCII "AutoMap"
0012ED7C   00000002
0012ED80   00000000
0012ED84   00000030
0012ED88   00000000
0012ED8C   6FDC96B0  ASCII "Scan"
0012ED90   00000002
0012ED94   00000000
0012ED98   00000034
0012ED9C   00000000
0012EDA0   6FDC96A8  ASCII "Pops"
0012EDA4   00000002
0012EDA8   00000000
0012EDAC   00000038
0012EDB0   00000000
0012EDB4   6FDC96A0  ASCII "PopPad"
0012EDB8   00000002
0012EDBC   00000000
0012EDC0   0000003C
0012EDC4   00000000
0012EDC8   6FDC9698  ASCII "Files"
0012EDCC   00000002
0012EDD0   00000000
0012EDD4   00000040
0012EDD8   00000000
0012EDDC   6FDC9684  ASCII "File1"
0012EDE0   00000001
0012EDE4   0000003B
0012EDE8   00000044                 <--- offset for beginning of file names
0012EDEC   00000000
0012EDF0   6FDC967C  ASCII "File2"
0012EDF4   00000001
0012EDF8   0000003B
0012EDFC   00000080
0012EE00   00000000
0012EE04   6FDC9674  ASCII "File3"
0012EE08   00000001
0012EE0C   0000003B
0012EE10   000000BC
0012EE14   00000000
0012EE18   6FDC966C  ASCII "File4"
0012EE1C   00000001
0012EE20   0000003B
0012EE24   000000F8
0012EE28   00000000
0012EE2C   6FDC9664  ASCII "File5"
0012EE30   00000001
0012EE34   0000003B
0012EE38   00000134
0012EE3C   00000000
0012EE40   6FDC965C  ASCII "File6"
0012EE44   00000001
0012EE48   0000003B
0012EE4C   00000170
0012EE50   00000000
0012EE54   6FDC9654  ASCII "Dt1Mask"
0012EE58   00000002
0012EE5C   00000000
0012EE60   000001AC
0012EE64   00000000
0012EE68   6FDC9508  ASCII "Expansion"
0012EE6C   00000002
0012EE70   00000000
0012EE74   00000020
0012EE78   00000000
0012EE7C   6FDC5404  ASCII "end"
0012EE80   00000000
0012EE84   00000000
0012EE88   00000000
0012EE8C   00000000
[/code]
[/quote]

Near as I can tell this first chunk of data is pulled from memory in regards to memory location in d2 memory.  The second set however, is the formula pulled from the LvlPrest.bin (MPQ information)

For more information follow this link

That form is mostly about MPQ editing for creating D2 mods, but can also be very useful for understanding how maps work in Diablo 2.



Reading D2Data (MPQ)

To gather the neccessary .txt files I used WinMPQ (gotta love it) and programmed an automatic TextFile re-formatter for the file.  The text files you want to get a hold of are:
[code]
Levels.txt
LvlSub.txt
LvlPrest.txt
LvlMaze.txt
LvlTypes.txt
[/code]
These files can viewed by using Excel Viewer by Microsoft (good for win2000+)  These files are saved in a tabbed spreadsheet format.  Each column is seperated by a Tab (Ascii 09) character.  So if your good at programming its fairly easy to create a fileformat converter to retype these files in a better layed out  format.  I'll post my programs later for converting these files to a standard equally spaced text file, and to convert them to VB for coding later.

If have been adding NPCs/Monsters/Players/Merc/Summons/Objects to your arrays.  The only information you are missing is your map data.  Believe it or not, these maps aren't as random as you might think!  If you open your d2exp.mpq using WinMPQ and list all the *.ds1 files you will see there is only a set list of map options! 

For instance:  Rogue Town has 3 Possible Formats:  East, West, and South

[code]Filenames:
data\global\tiles\ACT1\Town\townE1.ds1
data\global\tiles\ACT1\Town\townS1.ds1
data\global\tiles\ACT1\Town\townW1.ds1[/code]

Now if we open up Levels.txt we will see a list of areas and their specific information.  Here you will see sizeX, sizeY. 

You may notice that although it says sizeX for Rogue Encampment is 56, if you try to walk across it you will see it is actually much bigger.  And if you run the .DS1 file through a d2 map editor [such as] you will notice it is actually a size of 285.  So what is going on here?

Well, the sizeX and sizeY are listed in Cell sizes (think tile sizes) not actual coordinates.  The tiles are actually in 5x5 coordinate chunks.  56x5 = 280.  But you might also note that the cells begin at 0 not 1, so I added another 5 for the cell not counted.

So now we know rogue encampment is actually at a size of sizeX 285, sizeY 205.  If you look into it furthur, you will find out that the players start location <b>varies</b> in each of the three town types.

If your town exits East, your Town Entry will be in <b>Cell (30,13)</b>, Corpse location at 32,13
If your town exits West, your Town Entry will be <b>Cell (26,24)</b>, Corpse location at 28,24
If your town exists South, your Town Entry will be <b>Cell (14,18)</b>, Corpse location at 14,18.

We can easily use this to build the default Rogue Map box in our minimap!  If we know our start location as a cell position, we can simply build the map around ourselves!

While in the .txt file:

You'll also notice a term DrlgType

[quote]
Paul Siramy Wrote:

[code]
1 = Maze
2 = Preset
3 = Outdoor
[/code]

Mazes are handled by LvlMaze.txt
Presets by LvlPrest.txt
Outdoors are a bit complex as their infos are in Levels.txt, LvlSub.txt and LvlPrest.txt.
[/quote]

In the case of Rogue Encampment the DrlgType is set to Preset.

Which means its going to load information from LvlPrest.txt


You'll also notice a term LevelType

This is which line from LevelTypes.Txt will be loaded for your current map level.

Now you might notice not all the .DS1 files are actually maps, but sometimes tiles for floors etc.  This is because our level will also be run through the LevelTypes.txt, which grabs a list of DS1's that can be used for floortiles, walltiles, etc.


Whats Next?

Well now we know that a preset list of map types exist.  And we know that these lists are interconnected.  So the wilderness connected to Rogue Town is a set size, and defined in the level*.txt files.  We also know that we can determine if the level is dynamic or static.  We also know that the objects are generated randomly, but can be detected by listening to our packets.  And we know that objects like trees, and large objects, are loaded from other .ds1 files.

One concept, what I'm doing now, is writing a quick program that processes each .DS1 file, and saves a small tabbed excel file with a 1 or 0 for each cell, as to weither or not the player is able to walk on that location.

You can gather map data using objects, reading process memory, reading the .txt files, etc.  If you have any working mapping techniques or corrections to make to my posting please shout and I will update it ASAP.

- KermEd.

[QUOTE]
If your town exits East, your Town Entry will be in <b>Cell (30,13)</b>, Corpse location at 32,13
If your town exits West, your Town Entry will be <b>Cell (26,24)</b>, Corpse location at 28,24
If your town exists South, your Town Entry will be <b>Cell (14,18)</b>, Corpse location at 14,18.
[/quote]

U must work with subtiles(5x5).
btw, entry location will be useless... we need know how acts the 07 packet to use the ds1 ^ objects matrix.

Right now I've managed to program a little utility that loaded all the .ds1 and .dt1 info and created files for me that contain only the pathing data.  Its a pretty simple utility, it just records the Length, Width, and then each byte represents a 1 or 0 for each subtile's pathing.  (0 being walkable).

I've found the memory locations for the map data too and have begun creating a pathing using the current room your in, as right now I have it running off those binary map files I created and getting the .ds1 to load from memory.

As soon as I have completed both projects I'll post the information on here.

One thing I've been looking at is marking the entire tile as walkable or unwalkable to save on memory space, but using the subtiles seems to work fine.  Maybe I'll make the pathing option as tiles or subtiles configurable in the bot depending on the users computer.

Peace.

flood fill technique will work fine ussing sub-tiles but all in this life can be a little better xD