Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / Help needed with more efficient code

Author
Message
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 23rd Oct 2003 02:26
Link
Ok heres whats going on...I have a text based map divided into 31 X 71 squares. I also have arrays for the total amounts of infantry, tanks, and air units allowed in the game. There are 1,000,000 elements for infantry, 1000 for tanks, and 1000 for air. Now when the cursor is over a square it goes through each of these array elements to see if any of the units is in that square. So for every one game loop the game has to look through 1,002,000 different array elements. This really slows things down. Can any of you think of a better way to determine how many infantry, tank, and air units are located at that square? Thanks.
Back to top
Profile PM
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 23rd Oct 2003 02:32
Link
Why not keep a count in another array for each type of unit. Every time you move a unit to that point, add it to the destination square count, and subtract it from it's source square count.
Back to top
Profile PM Email Website
zircher
23
Years of Service
User Offline
Joined: 27th Dec 2002
Location: Oklahoma
Posted: 23rd Oct 2003 02:57
Link
Or, create a user defined type to hold the unit info and then only create a 31x71 array of that UDT. I figure 1,000,000 elements of anything is a incredible waste of memory.
--
TAZ
Back to top
Profile PM Email Website
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 23rd Oct 2003 09:08
Link
I know 1,000,000 elements is a lot but I cant think of a better way to do this because each unit (infantry unit for example) could possibly each have a different weapons loadout.
Back to top
Profile PM
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 23rd Oct 2003 18:53
Link
Anyone have any other ideas? Thanks.
Back to top
Profile PM
Roger Race Bannon
22
Years of Service
User Offline
Joined: 21st Oct 2003
Location:
Posted: 23rd Oct 2003 19:00
Link
Hello,

I'm a C/C++ programmer and I'm new to DBPRO, but a way to solve it that could be faster is: Let the squares knew the elements it has.

[]'s
Back to top
Profile PM
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 23rd Oct 2003 22:29
Link
Roger, I dont understand what your saying. Could you elaborate a little more?
Back to top
Profile PM
TKF15H
23
Years of Service
User Offline
Joined: 20th Jul 2003
Location: Rio de Janeiro
Posted: 23rd Oct 2003 22:50
Link
I think I understand what he was trying to say. But it wouldn't work

I know a way to make this faster, but I'm not sure if it's what you want.(this is really hard to explain) If it's compatible with what I have in mind, you can split the 1,000,000 into four arrays of 1,000,000 each (or less, depending on how many infantry can fit on a single tile) and according to the infantry's position, they'd get moved from one array to another. that way, you would only check one fourth of what you were previously doing.

*looks around to see if anybody understood anything*

Morfy's Law - Enythink thet ken go rong willll.
Cole's Law - Thinly sliced cabbage.
Back to top
Profile PM Email Website
Roger Race Bannon
22
Years of Service
User Offline
Joined: 21st Oct 2003
Location:
Posted: 23rd Oct 2003 22:56 Edited at: 23rd Oct 2003 22:58
Link
Vandetta,

Create a structure to the squares. This struct should have some info about the square and maybe (as I told I'm new to DBPRO) some kind of array to hold the itens IDs.

The itens (infantry, tanks, and air units) should be one struct too.

The ID that's stored in the square array is the position this itens is on the array.

The code I wrote won't work under DB or C++, its just an example.

As u can see the itemID is the unit(s) that is on square.

The explanation is not very good I know (I'm at work, so I needed to write it fast )
[]'s
Back to top
Profile PM
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 23rd Oct 2003 23:26
Link
I think the only problem with that is arrays arent allowed inside of Types ( Equivalent to Structs ) in DBPRO.
Back to top
Profile PM
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 23rd Oct 2003 23:44
Link
I've just re-read your original post ...

It sounds like what you want is a set of linked lists - I'll see if I can put together an example for you tonight.
Back to top
Profile PM Email Website
Scorpyo
23
Years of Service
User Offline
Joined: 26th Aug 2002
Location: italy
Posted: 24th Oct 2003 00:03
Link
If each tile would contain a maximum number of elements( like 100), you could array your tiles : 31 x 71 = 2201
like : dim tiles(2201,100)

and keep track of the unit numbers in each tile in the 0-100 dimension of the array.
that way you would only scroll through the 100 elements of that tile when you are on it.
You could number infantry from 1 to 1.000.000, planes from 1.000.001 to 1.001.000 and tanks from 1.001.001 to 1.002.000
just an idea..
cheers
Back to top
Profile PM
QuothTheRaven
23
Years of Service
User Offline
Joined: 2nd Oct 2002
Location: United States
Posted: 24th Oct 2003 00:14
Link
...

make an individual level array for each unit type

where the cursor is, simply check the value of the cursor's position with the other arrays. For instance, if the cursor is at point 5,5, check the tank array at 5,5 and see what number is there. If the number at tank(5,5) is say, 3, then you know there are 3 tanks on that tile. Then repeat for each other unit.

For levels that un-needidly large, you'd probably want to random generate these numbers.

Back to top
Profile PM
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 24th Oct 2003 00:28 Edited at: 24th Oct 2003 00:28
Link
... use this code ...

I've implemented a doubly-linked list for this because it makes manipulation of the list easier.

Each tile has a 'pointer' that records the unit number of the last unit added to that tile. -1 is used to represent an invalid unit (ie, no unit).

Each unit has two pointers that records the unit immediately prior and after in the list. Again, -1 is used to represent an invalid unit. This only appears at each end of the list (Imagine a row of people holding hands - the ones at the ends will each have a hand free).

There are basically 5 functions here. Two to set up the tiles and units, two to add and remove a unit from a tile, and a last one that lists the contents of a tile.

This last one is the one you should make variations on to loop through the contents of a tile for checking your units.
Back to top
Profile PM Email Website
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 24th Oct 2003 05:20
Link
Thanks IanM, Im currently disecting your code to figure out how everything works. One thing, Im not familiar with the command array count and heres what the help file says:
Quote: "This command will return the number of items in the array. This is usually the value used to create the
array when the DIM command was used, however by modifying the dynamic array this value can change
throughout the execution of the program.
"


Now wait one darn tootin minute. Does that mean I dont have to create an array of 1000000 elements? Can I create an array and add on new elements as I need them? What is all this dynamic array stuff?
Back to top
Profile PM
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 24th Oct 2003 05:28
Link
Hmm...is there a bug with array count? Look at this code:
Quote: "dim a(5) as integer
print array count(a())
wait key"


It prints 5, but there are 6 elements in the array 0,1,2,3,4, and 5. What exactly does array count do since it obviously doesnt return the amount of array elements.
Back to top
Profile PM
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 24th Oct 2003 05:56
Link
Ok correct me if Im wrong, but I think your code IanM requires that the units in the units array be in sequence. For example, on tile (0,0) all units in that tile would have to be in the unit array's elements 5,6,7,8 and 9. Then another tile would have to be in array elements 1,2,3, and 4. Is this right or did I interpret your code wrong?

If this is the case I dont think I can make it work because units for each tile will be scattered through out unit array. So one unit for tile 0,0 will be at array element 12, but than another unit on the same tile might be at array element 500.

Let me know if Im right in regards to what I came up with your code? If I am is it possible to have an array for each tile? Im not talking about unit array(31, 71, x) Im talking about an actual array for each tile. That way I could dynamically add and subtract elements from the array. So when I put the cursor over a tile without any units it will only have to look at a zero dimensional array instead of an array with 1000000 elements. Is this possible?
Back to top
Profile PM
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 24th Oct 2003 12:05 Edited at: 24th Oct 2003 20:25
Link
The array count function tells you the highest numbered array item available, so looping from 0 to this number will visit every array item.

You can assign units in any order you wish - you can even leave them unassigned. Try it yourself, add unit 100 to the tile, or unit 54, or unit 77. In other words, yes, you have misinterpreted the code

If you decide to use dynamic arrays, you may have complications to deal with - if you insert or delete units, this changes the unit numbers of all units from that point in the array. I suggest that if you want to do something like this that you maintain a list of 'free' units in another array, and only expand the unit array when this list is free.

I'll expand the example to do this for you if you want - when I get home from work later today (about 6 hours)

[edit]re-reading your last point, the answer to that is no, you can't create an array of arrays (known as a jagged array), but the linked-list gives you the same features - an expandable list of units attached to the tile

I will still do the expanding unit array for this code.
Back to top
Profile PM Email Website
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 24th Oct 2003 12:29
Link
Thanks IanM, your going way out of your way and I really appreciate your help. Im going to go look through the code you posted above some more and see if I can figure out how it works.
Back to top
Profile PM
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 24th Oct 2003 21:47
Link
I've added a few routines to allow you to create and delete units on the fly. Also, I've added another function that simply empties out and deletes all units allocated to a single tile
Back to top
Profile PM Email Website
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 24th Oct 2003 22:00
Link
WAIT A MINUTE!! I think I undersand your original code. Genious! ABSOLUTE GENIOUS HAHA!Thanks.
Back to top
Profile PM
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 24th Oct 2003 22:20
Link
Hooray!
Back to top
Profile PM Email Website
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 26th Oct 2003 23:51
Link
CRAPOLA!

IanM, I made the changes you suggested but it runs incredibly slow and I cant figure out why. I've attached the entire code of my program. Run it and place the capital, you'll notice the number printed to the screen ( the number of infantry there) flickers. Now change
Quote: "Inf=RND(10)+1"
in the GenerateCapitalArmy() function to
Quote: "Inf=RND(10000)+1000"
and notice how incredibly slow the process of counting the infantry on the capital tile runs.
Back to top
Profile PM
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 27th Oct 2003 00:08
Link
Its because you aren't controlling the syncing of your program. If you don't do it, DBPro will do it for you ... right in the middle of your heavy processing.

I quickly tried putting a few syncs into place, and couldn't get it to draw properly for some reason, so I gave up on that. What I did instead if to put a SYNC ON at the top of the InfCount() function and a SYNC OFF at the bottom. Now it counts in a reasonable time



I don't suggest that you use this as the fix though ... change the code so that you have full control over syncing
Back to top
Profile PM Email Website
Vandetta
23
Years of Service
User Offline
Joined: 17th Dec 2002
Location:
Posted: 27th Oct 2003 00:44
Link
YOU ARE A FREAKIN GENIOUS! Thanks a lot IanM, you've really gone out of your way to help me out. I was ready to give up on the code but now it is working great!
Back to top
Profile PM
Back to top

Login to post a reply

Server time is: 2026-07-26 17:36:50
Your offset time is: 2026-07-26 17:36:50