Cheat Engine Forum Index Cheat Engine
The Official Site of Cheat Engine
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 


Big complex hack. Will this be too heavy?

 
Post new topic   Reply to topic    Cheat Engine Forum Index -> General Gamehacking
View previous topic :: View next topic  
Author Message
LongBeardedLion
Expert Cheater
Reputation: 0

Joined: 10 Apr 2020
Posts: 136

PostPosted: Tue Sep 15, 2020 3:01 am    Post subject: Big complex hack. Will this be too heavy? Reply with quote

Im planning to make a major hack. Until now i did small things.

i need your opinion to know if this will be too heavy on the memory, or if it is somehow unfeasible.

My game is the good old rts Age of Empires 2.

In the game, there is this unit, Monk, that can convert enemy units. So they become your units. But you must micro them, and click on each unit you want to convert, or else they just sit around.

My objective is to make my monks autoconvert enemy units.

The way im planning to do this. I dont know if it is the most practical way, and would like to know what you think, or if there is a better way.

1- Get my Monk unit position.

2- Go through the enemy units lists, and get each one of their units.
Then make a loop and get into an array the map position of each one of their units.

3- Calculate the square root distance between my Monk and each one of the enemy units (200+ enemy units). Get the ones that are close/within the range of my Monk conversion attack.

4- Call the function to convert one of the enemy units. If there are any closeby.

5- Loop and repeat the above every 2 seconds.

So my question really is. Looping through 200+ units positions, and comparing each one of them with the position of my Monk. Isnt that expensive for the computer? How efficient is that?

Also im planning then to apply this to a group of Monks. Like 10 monks. So that would be checking the locations of 200+ units * 10 monks / every 2 seconds. That would be even more heavy, no?

Should i go for this? Or this is crazy, and it wont work, because too much calculations and resource demanding?

What else suggestions do you have if there are any?
Thank you. Cool
Back to top
View user's profile Send private message
ParkourPenguin
I post too much
Reputation: 81

Joined: 06 Jul 2014
Posts: 2723

PostPosted: Tue Sep 15, 2020 11:22 am    Post subject: This post has 1 review(s) Reply with quote

Well... let's take some rough estimates. Assuming the memory addresses you're accessing aren't in cache, it'll probably take a few thousand instruction cycles per loop iteration (not including the call to convert a unit, which should be relatively rare). 200 loop iterations in total means roughly 1 million instruction cycles spent on a single check. Given that processors run at a few gigahertz (> 1,000,000,000), it's not unreasonable to think that a single thread could run that check on the order of a thousand times per second - far more than what would be required.
It should be fine to sleep about 100ms between checks. The user won't notice the delay and the cpu will keep up just fine.

This doesn't include other optimizations you could make. Once you find a valid unit, I'm assuming you can exit the loop. It might be a good idea to keep track of which enemy units are closest and check them first next time.


Doing that check for every monk might go poorly if you write the code poorly. CPUs are fast, and it's quite likely a naive solution could still work; however, this would be a good time to start thinking about optimization, particularly for cache usage (this problem is definitely memory bound).
Search for "cache optimization" and you should get a lot of resources.

If you want extreme levels of optimization, this webpage, particularly chapter 2, might be a little advanced for beginners but contains a lot of good information. It makes the same algorithm 42x faster between v0 (a good but simple/naive implementation) and v7 (optimized implementation).
You don't need to go as far as that- just read it and learn why certain changes allow the cpu to do stuff faster. In your case, optimizing the algorithm itself would give better results (triangle inequality can prove some checks are unnecessary between monks), but that could get really complicated fast.

_________________
I don't know where I'm going, but I'll figure it out when I get there.
Back to top
View user's profile Send private message
LongBeardedLion
Expert Cheater
Reputation: 0

Joined: 10 Apr 2020
Posts: 136

PostPosted: Tue Sep 15, 2020 2:35 pm    Post subject: Reply with quote

Thank you penguin.

What about the plan itself, i terms of functionality, not the performance.
Is there any other alternative that pops into your mind?

Do gamedevs do it this way? Do they scan constantly for nearby units on each unit? Or there is a better approach?

I dont know why but it seems my idea is so primitive. But perhaps its truly the only way, and there is no real magic about it?
Back to top
View user's profile Send private message
ParkourPenguin
I post too much
Reputation: 81

Joined: 06 Jul 2014
Posts: 2723

PostPosted: Tue Sep 15, 2020 3:35 pm    Post subject: Reply with quote

Computers operate under a set of well defined, concrete rules- the contrary to abstract concepts so easily construed by people as simplifications from trifles unnecessary for everyday life.
It's easy to look at the screen and understand if two units are nearby each other, but the computer needs to know what nearby means. I think the solution you've given is good enough.

There are "better" ways of doing this. Collision detection is the more general form of this problem; however, I'd argue such algorithms and optimizations are an unneeded complexity if the simpler solution you've found is sufficient.

Maybe you could get incredibly lucky and find some structure the game maintains referencing nearby units.

_________________
I don't know where I'm going, but I'll figure it out when I get there.
Back to top
View user's profile Send private message
atom0s
Moderator
Reputation: 156

Joined: 25 Jan 2006
Posts: 8047
Location: 127.0.0.1

PostPosted: Tue Sep 15, 2020 3:48 pm    Post subject: Re: Big complex hack. Will this be too heavy? Reply with quote

LongBeardedLion wrote:

So my question really is. Looping through 200+ units positions, and comparing each one of them with the position of my Monk. Isnt that expensive for the computer? How efficient is that?


Not very expensive at all to be honest, just be sure to have early-exits in your loop to skip unneeded processing whenever possible. Things like:

- Check and ensure the entity is something that can be converted. (ie. a tree vs. an enemy if the game shares a full block/list with everything.)
- Check and ensure the entity is alive and valid.
- Check and ensure the entity is within a given range, if not just skip further processing on it.

Long as you give the code every possible means of exiting early and avoiding doing more work on something that can be excluded fast, it shouldn't be an issue at all.

If speed does become a factor and something you really have issues with or care about, you can also look to using SIMD style instructions while performing the checks and calculations. Since calculating a distance requires doing the same thing on multiple coords, you can make use of SIMD for faster compute/calculations. (There are also other tricks that can be done depending on if you are doing 2D or 3D calculations etc.)

LongBeardedLion wrote:

Also im planning then to apply this to a group of Monks. Like 10 monks. So that would be checking the locations of 200+ units * 10 monks / every 2 seconds. That would be even more heavy, no?


Same thing as above, but you have options to start optimizing loops and caching information if you are going to be checking across multiple positions. This can also be further optimized depending on how the map is laid out and structured as you can ignore checking certain monks altogether if you can determine if they are in a location where nothing could possibly be due to being on a certain area of the map. If you can predict movements to any degree and can determine assumptions based on that kind of data, you can skip loops/checks if you know, for example, if your monk is in the bottom right corner of the map, and all possible convertible objects are completely nowhere near you and won't be for a given number of frames.

A lot of the more specific optimizations will land up coming down to what information is available, what kind of predictable data can be assumed, and how the game is laid out along with it being 2D/3D etc.

Concepts and such like the following could be useful:

- https://gameprogrammingpatterns.com/spatial-partition.html
- https://software.intel.com/content/www/us/en/develop/articles/program-optimization-through-loop-vectorization.html
- https://www.bogotobogo.com/Games/spatialdatastructure.php

A great thing to look for regarding this, since its virtually the same thing, is methods of collision detection and ways to optimize that.

Some other things to look into is better ways to store the data to be processed for higher performance algorithms as well. It can land up being faster to loop and store all entity data each frame into a newer data structure setup, then process it for your goal. While it may seem like more steps/work, the end result could be much faster in the long run.


Something else I'd suggest, if you are still working within CE itself, it may be time to shift your mod to a self-made module (injected DLL for example) instead. You are going to land up with a bunch of overhead using and relying on Cheat Engine depending on what you are doing. (ie. using Lua vs. auto-assembly etc.) This would be much easier to work on and maintain as an injected DLL into the game, as well as having full-on direct memory access removing any API call overhead and such.

_________________
- Retired.
Back to top
View user's profile Send private message Visit poster's website
LongBeardedLion
Expert Cheater
Reputation: 0

Joined: 10 Apr 2020
Posts: 136

PostPosted: Tue Sep 15, 2020 5:01 pm    Post subject: Reply with quote

Thank you atomos.

Both your answers were great. I gave reputation to Penguin, now i cant give anymore Sad.

There should be a way around this Razz

Quote:

Some other things to look into is better ways to store the data to be processed for higher performance algorithms as well. It can land up being faster to loop and store all entity data each frame into a newer data structure setup, then process it for your goal.


One thing i did in another exercise, similar to what you are saying. I needed a certain action to happen when a villager is on a resource like a tree or a gold mine, and that resource hits a certain number.
So instead of doing the most intuitive thing, that is to check all the resources address in the game, then checking their quantity, then performing the action. I did this:

1- Found the function that wrote to that type of resource. Detour it with a cmp for a number that i need the action to be performed.
2- Check who is mining that resource. Cmp with the properties of the villager that im looking for.
3- Save all the registers that are volatile.
4- Call a function. Make some other additional checkups if needed.
5- Start a new thread, that makes villager perform a specific action.

This works very well. Because, it will only do something first IF the gold mine or the tree is on a certain number, to start with. If its not then it wont even bother anymore. But if it is the number we want, then it will make another check, and another check. And only then will perform the action.

I really appreciate that you made me reflect on this. Because this can be 10 times better.

I can simply do this:

1- Hook the function that writes to all units positions.
2- Cmp if the X and the Y is within a certain distance. Or make square roots, and check if the distance is below a certain number. If not, it stop right here.
3- If yes. Then check if it is an enemy or an ally.
4- Check if it is a soldier that we are interested in.
5- Convert.

Seems great too. And it doesnt loop through every single unit to start with. But on the other hand it needs to perform a square root calculation for each unit in the game, i dont know how economical that is. Since before i didnt have to make any square root, it was just a simple cmp with a number.

While on a similar alternative to my original idea in the first post:

1- Loop through all units.
2- Check if they are ally or enemy.
3- Check if they are a soldier that im interested in.
4- Check their position, square roots, and compare to my original unit to see if it is below a certain distance.
5- Call function to convert unit.

Now that i look it seems this last one is also great Rolling Eyes Shocked
Thank you though Smile
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Cheat Engine Forum Index -> General Gamehacking All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2005 phpBB Group

CE Wiki   IRC (#CEF)   Twitter
Third party websites