[guide] fetching stuff in gameobject lists without looping

[Interest07]

Come to think of it, there is one case where uniqueIds stay the same and could be interesting to look up without traversing a list. That would be resources, I know I keep a blacklist of certain resource's Ids that are put inside trees or buildings, because it looks a bit fishy when I'm harvesting/mining those. Then again, when you're flying about harvesting resources, you have plenty of time to traverse a list, even though it's 769 entries long

[zenvoid]

Hehe, well, let me see.. where to start.

First of all, i have no clue how lookup into a hashtable became about
saving information about objects persistently. That's nonsense really, in this
context.
The original post was to point out, that there is a short-cut to looking objects
up inside the hashtables, and gave an algorithm to do so. Simple.
The implementation was done in ~30 mins, so bear with me if it was not
very effective, it was not meant to be, it was meant to be illustrative.

Second, wether the object Ids change from server instance to instance is
irrelevant to this topic. Given an objects id, it is a matter of doing the hash
calculation and asking the list to present the reference it has to the object
with that particular hash.

@Shareen
No, you misread. I stated that there is a way to always have an objects Id,
and that is by hooking the InsertFunction in the client. Interest07 pointed
out that an even better source would be the RecieveMessage function.
There are magnitudes more data to sift through there, but he's absolutely
right.
The main point was, that there is a way to obtain the object Id without
looping the entire list, and that given an objects Id, you can always find
it in the hashtable via a quick calculation, also without looping.

regarding the hashing function:

There is not alot of "science" involved in the hash calculation. It's pure
mathematics.

objectOffset = listBase + (objectId % listHashSeed) * 4

this calculation is present in the client too, as i stated in the original post.
The listHashSeed is a variable obtained from inside the list class structure.

There is no way to go back, if you have the hash for a particular object,
you cannot obtain the Id. When you compute an objectId's hash, you loose
information about the Id in the process. This is the whole point of doing
it. You compress the data into something useful, like using it for indexing
a list, hence the word HashTable.
I won't go further into the reasons for choosing a hashtable, but if you're
interested i recommend MSDN's guide on data structures.

about object Id's

An objects Id is not assigned at random, you will always be able to get
an objects type from its Id. Like so:

	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;
	}

This is analogous to the code in the client, which tests wether an objects
Id contains a monster or item flag. This code is repeated inside the client
ad nauseum.

mov edx, dword ptr [esp+dwId] ; edx = objectId
mov esi, edx
and esi, 0x80000000
jz @objectIsTypeMonster
test edx, 0x40000000
jz @objectIsTypeItem

I would say that, that is quite a bit more than "absolutely nothing".
I havn't researched if the Ids contain other flag bits, since i havn't found
a use for it yet

Anyways, if done right, there are only a few times where you would need to
loop over the entire hashtable:
1) at startup of the bot
2) enter/exit instance

[vuduy]

Originally Posted by zenvoid

Second, wether the object Ids change from server instance to instance is
irrelevant to this topic. Given an objects id, it is a matter of doing the hash
calculation and asking the list to present the reference it has to the object
with that particular hash.

The relevance here is that how do you retrieve/get the objects Id in the first place? Do you get it from a static storage? Do you get it from parsing the list? If it's the first then it is guarantee to change frequently if your game server implements channels (ie. realms) like JD, ESO, and all the newer games; for PW, it changes less frequently but it does change from time to time. If it's the later then you are already parsing the list anyway.

The only scenario where this method becomes useful is if your bot is an aggro bot. No intelligence whatsoever; only fight with mobs that aggro'ed you. Then yes, you get the uniqueId from the TargetId offset, and you can retrieve the object structure directly from the hash table. This is the only time when the uniqueId is reliable to use as a lookup reference.

[zenvoid]

There is only one place the client could get information about the objects
it needs to render, and that is from the server, and thus the incoming
message queue.
If your bot was eavesdropping on that particular function, you would be able
to aquire the Id of anything the client keeps track of, its all a matter of
deciphering the packet contents.
Here's an example:

- Your botted char X is sitting in some spot in the world
- Mob Y spawns within your characters radius.
- The server communicates this to your client via the internet (d'uh)
- Your client recieves this information in the form:
- "Thou shalt render Mob Y, at position Q, and henceforth this object shall be
known to all as ID"
- The client then obeys and adds Mob Y to the internal hashtable of all mobs
- The Graphics Engine Loop enumerates the relevant lists to prepare the next
frame for rendering.
- And voila, Mob Y appears on your screen as if by magic, in the exact spot
the server told your client.

You as a player know that Mob Y is supposed to pop there, at that time,
from experience or google. To the client, its just yet another mob with
no history and no connection to the mob your bot just killed in that spot 2 mins ago.
To your client it's just an object with a unique id, that it needs to keep track
of.

The server is however not happy with Mob Y, so a decision is made. Mob Y
must start to walk.

Server sends this information to your client:
- "ID started moving from Q in P direction at speed S"
- again your client starts working on obeying the server, and renders Mob Y,
which it only knows as ID, to your screen. Along with a bunch of other crap.

There's no saved static file filled with useless Id's of mobs that may or may
not be present. Examining what your client receives, is all you'd ever need
in terms of figuring everything else out.

Now, it should be plainly obvious that if you were to insert some code at
either InsertObject or somewhere else near where your client processes
information from the server, will always net you an Id, because thats the
only information your client needs to obey the server, regarding objects
in the world.

Not to be confused with static stuff that constitutes the world, like buildings
and trees, rocks and so forth. In this sense, they're not world objects, they
are part of the terrain.
No sane coder is gonna make the server send out information like
"building 545342/6 is still standing in the exact same spot".

All this doesn't mean that looping through whatever list you prefer to use isn't
good enough. As Interest07 says, when your bot is gathering, you have
plenty of time for examining lists.
That's another way of saying: don't optimize on code that is not at the core
of the task you are performing.
If you don't need to look up objects in the lists because you have their Id
already, don't do it.

However, save for a few brave souls, nobody seems to want to share what
they discover. Who knows? Someone might come along one day, with a need
to look up an object in any of the lists, and find this post useful.

[vuduy]

Umm, if you are talking about hooking the receiving packets, then you do realize that server doesn't just send the unique Id of the objects right? It sends all the information including the class Id, level, position, and some other important data along with it.

If anyone is actually able to hook to the receiving function (eg. the clientless bot someone posted earlier), then there is no need to ever touch the object lists at all - which makes your suggestion null.

[Shareen]

Originally Posted by zenvoid

There is only one place the client could get information about the objects
it needs to render, and that is from the server, and thus the incoming
message queue.
If your bot was eavesdropping ...


Now, it should be plainly obvious that if you were to insert some code at
either InsertObject or somewhere else near where your client processes
information from the server, will always net you an Id...

And you will store these Ids in some temporary table of yours.

Then, the following scenarios are available to you:
1. Loop your lists of Ids and lookup objects in the list to get extended details about it, those that are actually useful to you, say distance, hp, etc,...in order for your bot to decide what to attack or pick up.
Since number of Ids in your list is the same as number of monsters in the list, you will loop exactly same amount of times as if you'd skip Id gathering in the first place and just loop monsters list (real sized one, not 769 one).

2. Agro monster attacks your bot, you retrieve it's Id from target offset and do a direct lookup on the object without looping.
This gives you an advantage over looping monsters list. And yes, I do need to know exactly what is attacking me, because I can take down 2-3 monsters but not a world boss. I also need to know if attacker is already being hit by someone else, like my other bot running Tank character. If it is, then I can ignore it, it will switch. If not, I'll need to avoid and lure it closer to tank character, healers don't tank melee well.

3. Bot just killed a monster and loot dropped. You caught Ids of loot objects coming in and added them to your list. However, you can't just pick them up, since you don't know anything else about them. So you need to lookup objects by looping your list of Ids to see if:
- if item is loot of type bot is configured to pick up
- if item is your loot or the loot of someone killing near by
Still, you have an advantage here, since you do not need to loop 769 records, like already explained in my previous post.

Originally Posted by zenvoid

Not to be confused with static stuff that constitutes the world, like buildings
and trees, rocks and so forth. In this sense, they're not world objects, they
are part of the terrain.
No sane coder is gonna make the server send out information like
"building 545342/6 is still standing in the exact same spot".

I have already excluded buildings, with reasons given.

Originally Posted by zenvoid

... If you don't need to look up objects in the lists because you have their Id already, don't do it.

Ok, I'll correct my self for stating "Id tells you absolutely nothing about the object".
Correct way of putting it, obviously, would be: "Id tells you what type of object your are dealing with and it's index in the hash table can be calculated from it".

But this was never a question. Question is, what use do you have from it?
You've added another monster to your monster Ids list, so you know additional monster spawned.
I checked monster array count and get to the same conclusion.

You know it's a monster trough specific Id range, I know it's a monster because monster array size changed.

True, you can do a direct lookup on that monster and have it's details up in no time. But there isn't any point in doing that, any information regarding this monster needs to be evaluated to others around it, or you might end up running into a trap. So you need to loop your monster Ids list to do object lookups and I end up looping monster list to do the same.

Please, provide me with an example of use in an intelligent bot, maybe that will help me understand what you claim I seem to be misunderstanding.

Originally Posted by zenvoid

However, save for a few brave souls, nobody seems to want to share what they discover.

Oh, we tried, unfortunately we don't all share Interest07 patience

Originally Posted by zenvoid

Who knows? Someone might come along one day, with a need to look up an object in any of the lists, and find this post useful.

No doubt. Maybe they will find it even more useful when it's method and usage is explained in further detail.

Don't get frustrated so soon.

[Smurfin]

these are heavy stuffs my head spins after reading all the posts
good to know that we have genius people in game hacking here in this forum

sorry for the interruption...don't mind this post, just browsing the forum and passing by, hehe