[guide] fetching stuff in gameobject lists without looping

Page 1 of 2 1 2
11/15/2010 10:29 zenvoid#1
I havn't seen this anywhere on this forum, which is kinda odd, since it
should have been obvious to any programmer what is happening inside
the client.
At the end of the post i'll provide some C# code to access the 3 lists.

WorldObjects is my name for the well known player/npc/item lists.

First a little education.

The WorldObject lists inside elementclient are actually hashtables, which is
a special array, where you can turn a key into an index via a hashing
function.
This basically means that as long as you add key/value pairs with
unique keys, lookups into the table wil be O(1). That just means that the
time needed to find a specific element in the table is independent of the
number of elements in the table. Very smart.

Looping through a hashtable to find an element with a known key is..
well, not smart.

Right... moving on..

To find an object with a known key inside the client, one would need the
hashing function and the hash seed. Luckily, those are both provided in
the code of the client (well, d'uh).

Code:
mov esi, [esp+dwId]
mov eax, esi	
xor edx, edx	
div dword ptr [ecx+24h]
mov eax, [ecx+18h]
mov edx, [eax+edx*4]
The first thing we need to calculate the index of an object, is the hash
seed for that particular list. Easy (pseudo-code):
Code:
seed = [[[[BaseAddress + 0x1C]+ 0x8] + ListOffset] + 0x24]
arrayStart = [[[[BaseAddress + 0x1C]+ 0x8] + ListOffset] + 0x18]
ListOffset is the offset for the specific list you wish to search in,
currently (Player = 0x20), (Mob = 0x24), (Item = 0x28).

Alright, now for the calculation:
Code:
index = arrayStart + (objectId % seed) * 4
The % (modulus) simply divides x by y and returns the remainder.
The 'index' variable now contains a pointer to the list element that holds
information on the wanted object. List elements look like this:

 
dw 0
dw *worldObject
dw objectID

Code:
objectBase = [index + 0x4]
objectId = [index + 0x8]
There you go, from objectId to objectBase without any looping.

Some code taken out of context to access the lists:
The code won't compile unless you write your own methods to read
process memory. This is simple, and covered in a multitude of tutorials
around the net, this forum included.

Code:
public enum WorldObjectType
{
	Player = 0x20,
	Monster = 0x24,
	Item = 0x28,
}
public abstract class WorldObject
{
	public uint Id { get; private set; }
	protected uint BaseAddress { get; private set; }
	protected IntPtr hProcess;

	public WorldObject(IntPtr hProcess, uint id, uint baseAddress)
	{
		Id = id;
		BaseAddress = baseAddress;
		this.hProcess = hProcess;
	}
	public static WorldObjectType ResolveId(uint id)
	{
		WorldObjectType type;
		if ((id & 0x80000000) == 0x80000000)
		{
			type = WorldObjectType.Monster;
		}
		else if ((id & 0x40000000) == 0x40000000)
		{
			type = WorldObjectType.Item;
		}
		else type = WorldObjectType.Player;
		return type;
	}

	public static WorldObject GetObjectById(IntPtr hProcess, uint baseAddress, uint id)
	{
		WorldObjectType woType = ResolveId(id);
		WorldObject output = null;
		// standard stuff
		// baseAddress is the so called real base, whatever you wanna call it, as of 15. nov its 0xA5B90C in PWI
		uint pointer = Memory.GetUintAt(hProcess, baseAddress) + 0x1C;

		// WorldObjects class, contains the 3 lists for world objects
		pointer = Memory.GetUintAt(hProcess, pointer) + 0x8;

		// WorldObjectType enum resolves to list offsets, smart huh? right... moving on.
		pointer = Memory.GetUintAt(hProcess, pointer) + (uint)woType;

		// hash seed pointer for the selected list
		uint hash = Memory.GetUintAt(hProcess, pointer) + 0x24;
			
		// hash seed
		hash = Memory.GetUintAt(hProcess, hash);

		// sequential list of pointers to listEntry objects
		pointer = Memory.GetUintAt(hProcess, pointer) + 0x18;

		// now, pointer contains the base of the array
		pointer = Memory.GetUintAt(hProcess, pointer);

		// hash function, this converts a given id to an index into the correct list.
		uint index = pointer + (id % hash) * 4;

		// base of this particular list entry
		uint listEntry = Memory.GetUintAt(hProcess, index);

		// pointer to the object desired
		uint objectBase = Memory.GetUintAt(hProcess, listEntry + 0x4);

		// the id of an object is stored directly inside the list entry struct
		uint idImm =  Memory.GetUintAt(hProcess, listEntry + 0x8);

		// instantiate a WorldObject object, according to type
		if (woType == WorldObjectType.Monster)
			output = new Monster(hProcess, idImm, objectBase);
		else if (woType == WorldObjectType.Player)
			output = new Player(hProcess, idImm, objectBase);
		else output = new Item(hProcess, idImm, objectBase);

		return output;
	}
}

public class Monster : WorldObject
{
	private const uint HpOffset = 0x12C;
	private const uint MaxHpOffset = 0x16C;
	public uint Hp { get { return Memory.GetUintAt(hProcess, base.BaseAddress + HpOffset); } }
	public uint MaxHp { get { return Memory.GetUintAt(hProcess, base.BaseAddress + MaxHpOffset); } }

	public Monster(IntPtr hProcess, uint id, uint baseAddress)
		: base(hProcess, id, baseAddress)
	{
	}
}

public class Player : WorldObject
{
	private const uint HpOffset = 0x474;
	private const uint MaxHpOffset = 0x4B4;
	private const uint MpOffset = 0x478;
	private const uint MaxMpOffset = 0x4B8;

	public uint Hp { get { return Memory.GetUintAt(hProcess, base.BaseAddress + HpOffset); } }
	public uint MaxHp { get { return Memory.GetUintAt(hProcess, base.BaseAddress + MaxHpOffset); } }
	public uint Mp { get { return Memory.GetUintAt(hProcess, base.BaseAddress + MpOffset); } }
	public uint MaxMp { get { return Memory.GetUintAt(hProcess, base.BaseAddress + MaxMpOffset); } }

	public Player(IntPtr hProcess, uint id, uint baseAddress)
		: base(hProcess, id, baseAddress)
	{
	}
}

public class Item : WorldObject
{
	public Item(IntPtr hProcess, uint id, uint baseAddress)
		: base(hProcess, id, baseAddress)
	{
	}
}
Usage:

Code:
	WorldObject wo = WorldObject.GetObjectById(TargetId);
You need to cast to the correct WorldObject type to access the
extended members like so:

Code:
			
	Monster m;
	Player p;
	Item i;
	if (WorldObject.ResolveId(wo.Id)== WorldObjectType.Monster)
		m = wo as Monster;
	else if (WorldObject.ResolveId(wo.Id)== WorldObjectType.Player)
		p = wo as Player;
	else i = wo as Item;
or do a direct type check on the returned object:

Code:
	Monster m;
	Player p;
	Item i;

	if (wo is Monster)
		m = wo as Monster;
	else if (wo is Player)
		p = wo as Player;
	else i = wo as Item;

The WorldObject class and it's subclasses are stubs i wrote in a hurry,
go nuts with CE if you feel like expanding them. Do notice that the
offsets for other player's info are the same as the local player :D

The code has been tested to work with player list and monster list,
item list is untested, but there is no reason it should not work.

Do also notice that, fetching stuff from lists with this code is intensive,
there are alot of calls to ReadProcessMemory. A smarter and quicker way
would be to inject a function into elementclient.exe that writes the
objectBase to a shared memory (gotten with VirtualAllocEx), and check
there once the function returns. I might post my inject function later if
anyone feels a need for it.

Feel free to alter, use and abuse the code in any project you want to.
Feel free to ignore this entire post.

Cheers.
11/15/2010 12:32 Interest07#2
Thanks for this guide. I have to point out though, that the main reason people are looping through the lists, is to get the objectId in the first place. But I can imagine this being useful in some cases for sure and it was a very well written guide ;)
11/15/2010 14:52 zenvoid#3
@Interest07
Agreed, looping through the list is necessary in some cases. And thank you
for the comment. Your own posts and tools have been most helpful in
getting up to speed regarding this particular mmo client.

The problem is, there is no actual need to loop the lists if you have
and objects id. The reason we don't always have this, is because we don't
pay attention.

There is another function in the client of as much use to us, as
GetObjectById, and that is InsertObject :)
Hook that function, and dump the object Ids where ever you like, and your
need for looping the lists has gone. You could be even more hackerish,
and only dump object id's of objects you are interested in, like, for
instance gold piles, or materials.
Every time your hook alerts you to a new item, you fetch it from
the corresponding list, and do a PerformAction(pickup) :)

I'm still researching the WorldObject class in the client, but the project plan
for this little adventure is something like this:

1) find InsertObject
- working on it
2) hook it and dump Id's to a shared memory resource
- can be done with outgoing packets quite easy.
3) make the hook code signal your bot once a new item is inserted
- You can do this via the Mutex class inside kernel32.dll
4) react based on character state

Code:
if (IsBusyDoingSomething)
  QueueItemForPickupLater(id);
else Pickup(id);
5) make bot code run entirely inside the clients address space via CreateRemoteThread
- this eliminates the need for ReadProcessMemory and WriteProcessMemory
except for keeping your bot UI updated, which in turn relieves the stress on
multi bot systems :)
11/15/2010 16:16 Interest07#4
Ahh, that would indeed be a clever to go about it hehehe ;)

Although I suppose hooking at the receive packet point would be even better? As that would grant you all the information you need really.
11/15/2010 17:46 zenvoid#5
Yeah, problem with the incoming packet queue is the amount of packets
recieved i have no use for.
But you're right, it really is just a matter of where in the chain you extract the information you need. An incoming packet hook could serve later on :)
11/15/2010 21:48 BuBucekTop#6
Peronally I prefer to make an LSP-module transparently catching and decoding both outgoing and incoming packets. After that you can forward 'em (or even control packet flow) to your host app, e.g. your bot.
And after all you can make your host app entirely script-based FSM. Which in my oppinion will be the best option.
11/16/2010 06:01 vuduy#7
Any intelligent bot would require looping through the lists for filtering purposes. For example:

1. Targeting a specific monster class Id, level, or name, or by distance, etc
2. Picking up specific items or item names, item types, etc...
3. Selection of players from guild and/or clans, friends, enemies, etc...

Even if you are hooking the InsertObject, you are actually looping through the lists because if the game client inserts 100 objects, you are actually processing the same 100 objects hence the same as looping through the lists (although only once - but that can also be achieved by caching).

If you want to focus on performance and efficiency then it is better to design a caching mechanism for these lists (as well as objects) so that you don't have to recreate them over and over again. Everything boils down to the baseaddress of the object; if it remains the same, then 99.9999% that it is the same object and no need to be recreated.
11/16/2010 19:40 zenvoid#8
@BuBucekTop

My bot already runs 100% on scripted code, which can be altered and
recompiled during runtime. In theory i could have the controller stop-recompile-start
the slaves at leasure.
How to control the bot-net is another matter, and a matter of taste i suspect.

@vuduy

You're absolutely right, looping cannot be avoided completely, but as you
said, you'd only have to examine a subset of the complete set.
The thing that irks me the most in the code i have seen so far is looping
over the lists with a valid Id already in hand.
Keep track of the incoming information to the client, and make intelligent
decisions based on that. You don't need to examine base addresses if you
know for certain that an object has been deleted.
I havn't been working on this client for very long, so lets see how far i come
before i hit the wall :)
11/16/2010 21:53 vuduy#9
I find it strange that anyone would use the unique Id statically. These Ids are generated per instance of the game server and they are usually not the same whenever the server/instance restarts.

The Id that you are supposed to work with is the class Id for NPC, and item class Id for items. As for players, it is easier to identify by using the player's name instead of Id. Therefore, you shouldn't ever be looking up objects using its unique instanced Id at all.
11/17/2010 00:28 zenvoid#10
@vuduy

I wasn't talking about saving the Ids permanently :)
My point is, that looking through the lists for an object or type of object you
may need isn't really needed if you know for a fact that they're there. Or isn't.
By that i mean that you know this because you peeked the message
queue, and noted an object of interest, not that you saved it in your ini file
to avoid doing actual bot logic programming.

The id of a particular object instance is only important if you need to find it
in the list. Once the object has been dealt with (killed, picked up, whatever),
the Id ceases to be of any relevance. Until next time it arrives at the incoming
message queue, at which time the bot will decide what to do yet again.

If you're doing a static "leashed to a point on the map, killing everything in
raduis R, and quit when PMed" kind of bot, mob types matter more,
and looking up stuff matters less.

But if you're doing a multi client botted dungeon run, with a bot veno pulling,
it becomes important to look up stuff in the list to check distances, not just
to your puller, but also to other mobs.
11/17/2010 02:07 vuduy#11
Huh? What the heck are you talking about? I'm questioning why would anyone be looking up an object by the unique instance Id? That Id has no information whatsoever.

You're making a point that people are wasting efficiency by looping through the lists to find the unique Id because it can be directly accessed by the hash table. I am making a point that why would anyone wants to search the object by this unique Id at all when it holds no valuable information.

Objects are searched by the names, class Id, types, levels, etc... where the information is actually useful. There is no use at all by searching the unique Id.
11/17/2010 07:56 Interest07#12
Quote:
Originally Posted by vuduy View Post
Huh? What the heck are you talking about? I'm questioning why would anyone be looking up an object by the unique instance Id? That Id has no information whatsoever.

You're making a point that people are wasting efficiency by looping through the lists to find the unique Id because it can be directly accessed by the hash table. I am making a point that why would anyone wants to search the object by this unique Id at all when it holds no valuable information.

Objects are searched by the names, class Id, types, levels, etc... where the information is actually useful. There is no use at all by searching the unique Id.
He means that when you for example build a bot to run an instance with (say an fb), you will always want to pull the mob with uniqueId x first, because you will always come across that mob first in the instance. So you can directly look up the stats of that particular mob without first traversing the list of mobs until you find one with the same uniqueId, or traverse the mob list to find the closest, since it will always be that particular mob.

At least that's what I got from it ;)
11/17/2010 08:04 vuduy#13
That uniqueId is not guaranteed to be the same every time for each instance; why would anyone use that Id as a lookup reference? That is like trying to lookup dynamic addresses statically.
11/17/2010 11:03 Interest07#14
Quote:
Originally Posted by vuduy View Post
That uniqueId is not guaranteed to be the same every time for each instance; why would anyone use that Id as a lookup reference? That is like trying to lookup dynamic addresses statically.
I've found them to remain as much the same as offsets remain the same in between patches? Then again, I've never done much in the manner of storing them for later use lol. But perhaps in instances they do vary, I'd have to check that.

I've also never had any efficiency problems, however inefficient my coding is.
I mean, updating lists and values is done in fractions of a second... I only check for new actions to perform every 500 ms or so. Therefore inefficiency is not one of my worries (I don't run a dozen bots and I'm not planning to), so I'm quite happy just browsing the lists personally.

edit: yup they definitely change around in instances. Okay now I'm definitely not sure what to use it for... Oh well I tried :D
11/17/2010 11:47 Shareen#15
Quote:
Originally Posted by vuduy View Post
That uniqueId is not guaranteed to be the same every time for each instance; why would anyone use that Id as a lookup reference? That is like trying to lookup dynamic addresses statically.
I am with vuduy on this one.

Quote:
Originally Posted by zenvoid
The id of a particular object instance is only important if you need to find it in the list. Once the object has been dealt with (killed, picked up, whatever), the Id ceases to be of any relevance. Until next time it arrives at the incoming message queue, at which time the bot will decide what to do yet again.
If I understood this properly, you turned looping trough list into an event driven process. Instead of looping and examining each object properties, you take Id and lookup that object properties by addressing it in the list directly.

However, like vuduy stated, I fail to see what has really been gained here. Since Id tells you absolutely nothing about the object, you end up examining every object, like you would when looping. In fact, given overhead with checking "arrives at the incoming message queue", it might probably run slower then loop.


Right.. something just hit me. There is one case where your "thing" makes sense.
You are assuming all lists are being looped from 0-768 (or something close), where existing object occupy a "record" in the list in the form of a valid pointer and not existing objects have a pointer of nil. Instead of looping trough entire list, only "jump" to records that have valid pointers.

I'm guessing your assumption based on your words: "many people on forum uses this...". While this may be correct, there are other lists, for players and npcs, which unlike 769 lists, are "real size" lists. So if there are 5 players around you, that lists will only contain 5 records and all with valid pointers. Same with NPCs.

For two remaining lists however (materials and buildings) where there is only 769 version available, your method could be debated.

So let's debate it.

Tackling buildings list is futile really, since same list can be obtained from files and is static, ie, buildings don't change, move or die.

Which leaves us with one, materials.
I do agree that jumping to only valid object records in a list is a time saver, we are still looping, however unlike full 769 loop, we only need to make as many loops as there are materials, and on average that number is far far lower than 796. Let's put it in the range of 20-25 for academic purpouses.

Next thing that boggles me however, is your implementation. Well, pseudo implementation. You mention hooking InsertObject to get piece of information (I believe you call it seed) to use in calculation to get Id (key). Further that key is used in calculation involving modulus and some multiplication, to get offset in the list for the object.

While it sure looks very scientific I find my self asking why?

You hooked InsertObject which returns seed (or Id or whatever you called it). Would it not be simpler to just retrieve the offset that object was inserted at?
InsertObject does in fact insert the object in the list (after it has created it first) so it would know the offset object will be placed at. Or some function being called after would.
Either way, you can get the offset directly without the need to run rather expensive modulus calculation on those seeds.
That is true even if you insist on having an Id, since you can grab it the way you already explained.
I do not know what use this Id can be to you when you already have the offset, but if you want it...
Page 1 of 2 1 2