Sign in to follow this  

Infinite number of units

This topic is 4302 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I was just having lunch, and suddenly i wondered about "how to make an array of units(strategy games e.g) that limitless if possible". :) For example, red alert series. You can produce units as more as you can. There is no population cap like age of empires series. Any suggestions?

Share this post


Link to post
Share on other sites
One day, a monk went to see his master, and asked:

My mainframe has limited memory, and cannot store enough polygons to render a forest of spheres. Pray tell, sensei, how can I work around this?

The old master pondered and answered:

Polygons need to be drawn, not stored.

And the monk was enlightened.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The Red Alert series does have a limit. It is just high enough that you wouldn't normally encounter it.

Share this post


Link to post
Share on other sites
Red Alert has other limits before that. In particular, there is something like a 50-unit limit on the amount of units that can be selected at any given time.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
One day, a monk went to see his master, and asked:

My mainframe has limited memory, and cannot store enough polygons to render a forest of spheres. Pray tell, sensei, how can I work around this?

The old master pondered and answered:

Polygons need to be drawn, not stored.

And the monk was enlightened.


Hmm, so red alert first checks if there is an unit in tile and if so, select it?

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
One day, a monk went to see his master, and asked:

My mainframe has limited memory, and cannot store enough polygons to render a forest of spheres. Pray tell, sensei, how can I work around this?

The old master pondered and answered:

Polygons need to be drawn, not stored.

And the monk was enlightened.


that is beautiful :D

did you make that up or find it somewhere? i'm totally putting that on my facebook ^^

Share this post


Link to post
Share on other sites
@justin: made that up.

@by: polygons are units, spheres are groups of units. You need to display polygons/units when a group/sphere appears on the screen. However, when they are not on the screen, you only need to memorize the group/sphere size and position, which drastically reduces the memory requirements.

This means that you'd need to store the ~100 units appearing on the screen, and 1/100th of other units (which would be assembled in groups of average size 100).
Using as much memory as Total Annihilation (200 units), you could store 100 + 100*100 = 10100 units.

However, Red Alert is still much within reasonable limits on unit count, so I don't see why it would use special technology to store its units (probably a resizable array, that's all).

Share this post


Link to post
Share on other sites
i am fairly certain that the Command & Conquer: Generals series does not have a limit. I guess one solution to this would be that once you get 100 guys you could combine them into 10 really strong guys. Then all you would have to do is increment their firepower, which I would assume would be a number and will not likely reach its max for a VERY LONG time. (you could repeat this process everytime you got 10 of a certine until but the actuall gameplay aspects would varry)

for example

100 foot soliders

become

10 super soliders

power of super solider 1 = [0-9].power
power of super solider 2 = [10-19].power

you could even do mixed unit strengths this way and even subclassify units based on their power.

char buf [10];
sprintf(buf, "%d", Solider.power / 10);
Solider.Name = "Solider Level " + buf;

something of that nature

EDIT: On the idea of infinity and computers: Computers will always have a finite amount of memory and processing power so if your truly talking about inifite units. You can't

Hmm so if we do the math...

100 lvl 1 = 10 lvl 2
1000 lvl 1 = 100 lvl 2 = 10 lvl 3
10000 lvl 1 = 1000 lvl 2 = 100 lvl 3 = 10 lvl 4

power of each lvl 4: 5000 (EASILY within the bounds of a simple int)
10000 units is insane, and you could get higher then that and not max out an int but if your curious as to the cealing go on ahead

Share this post


Link to post
Share on other sites
Um, the obvious solution is a linked list, not an array. Look up "linked list". A better solution is a linked list of arrays, since that's faster. You know, something like:


template <class T> struct listnode
{
_T Elements [256];
int NumElements;
listnode* Prev;
listnode* Next;
};


This combines the advantages of a linked list (infinite size) with the advantages of an array (speed).

EDIT: Memory is not an issue by the way. Let's say each unit is:


struct unit
{
point Location;
point Destination;
unit* Target;
int Action;
};


If point contains the floats X and Y, that's 24 bytes per unit. Then every megabyte of memory can theoretically store 43690 units. Obviously memory is not an issue and there's no point in trying to take shortcuts around storing each unit individually.

Share this post


Link to post
Share on other sites
Yes of course you would want to keep the structure for units small but think more about the processing power. imagine doing pathfinding algorithums for 43690 units then there is the drawing routines, animation, I really didnt inerperet the OP as asking about the best way to store units but I'm probably wrong

Yes Link Lists or vectors are the way to go not sure which though because in terms of drawing and animating you would iterate through all units (faster in a list) but selecting an individual or group of units would take longer in a linked list. Worse case senario is that you select the last unit on the list and it takes a long time to iterate through every unit until it gets to the last one.

Share this post


Link to post
Share on other sites
Quote:
Original post by CGameProgrammer
You know, something like:


[Ugly mess]


This combines the advantages of a linked list (infinite size) with the advantages of an array (speed).


  • A linked list is not infinite. It has a fixed number of elements at any time.
  • Both arrays and linked lists can be extended by adding at the end, both in constant time.
  • If all you do is remove elements from a container where order does not matter, and insert others at the end, lists have no advantages over arrays, and even have a size disadvantage.
  • An ID → object association (such as that provided by arrays) is a good thing to have in a multiplayer game.
  • A list of arrays already exists in C++ (deque), no need to reimplement it. And it's actually faster for the aforementioned purposes than both vectors and lists.



Share this post


Link to post
Share on other sites
Quote:
Original post by raptorstrike
imagine doing pathfinding algorithums for 43690 units


If these units are split up into 44 groups of 1000 units, then I can already imagine this cleanly.

Quote:
then there is the drawing routines, animation


[rolleyes] How many units do you expect to be on the screen at any given time?

Share this post


Link to post
Share on other sites
Extending an array by adding to the end is not constant time, surely? You would need to allocate new memory of the size you need, and then copy over the old elements - the latter should be order n.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Adding elements to the end of an array is amortized constant time. The simplest way to do this is to double the size of the array when it is out of space. If the array was size N, its new size will be 2N and there will be enough space for N more elements to be added in constant time. The time required to copy the old elements to the new array after resizing is O(N), but after that the next N insertions are O(1). So adding N elements requires O(N) time. On average, the time required is constant.

Share this post


Link to post
Share on other sites
Quote:
Original post by King of Men
Extending an array by adding to the end is not constant time, surely? You would need to allocate new memory of the size you need, and then copy over the old elements - the latter should be order n.


Depends on what kind of array we're talking about.

If we're talking about "C style realloc() to the current size + 1 every time you add something", then yes.

If we're talking about "std::vector style double-the-memory-allocated every time you run out of room", then no - it will be amortized constant time. Although any given call might operate in O(n) fashion, the occurance of those calls decreases as n increases as well.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by raptorstrike
imagine doing pathfinding algorithums for 43690 units


If these units are split up into 44 groups of 1000 units, then I can already imagine this cleanly.


Exactly. If you have that many units, then it's as simple as switching algorithms. Instead of using a more standard pathfinding algorithm, use/write one that calculates paths for groups of near units - there's tremendous potential for some locality-of-reference there.

Share this post


Link to post
Share on other sites

I think too that the memory isn't really the issue here. Nowadays you can easily reserve large amounts of memory for your units.

There are plenty of tricks for the AI. As it was mentioned already, you don't need to run the path finding for every unit. When there is 100000 pieces on the battle field, not all of them need to have exact information about everything. Consider military hierarchy, the grunts just follow sergeants who follow lieutenants and so on. So only unit who needs to do any pathfinding processing is the lieutenant and the grunts just need to avoid hitting any trees :)

Not all the units need to do observe the environment all the time. The group can be considered to have a sort of borg-style mind. If one soldier spots something and starts shooting at it, the others can starts shooting too at the same direction (knowing or without knowing what they are shooting at).

Share this post


Link to post
Share on other sites
Quote:
Original post by by
So, is it a good idea to use an array that has got very high limit that player shouldn't reach?


No, since you must allocate more memory than you need at the start, and there is the possibility of not having enough room, which seems to be against the spirit of the thread.

Just use the equivalent of std::vector, they are very fast, you probably wont notice the difference between a vector and an array in release mode.

Share this post


Link to post
Share on other sites
Well, i'm not using cpp for a long time :) I don't know about "std::vector". Can you tell me what is it? :))

Share this post


Link to post
Share on other sites
Quote:
Original post by by
Well, i'm not using cpp for a long time :) I don't know about "std::vector". Can you tell me what is it? :))


A resizeable array that will expand to your needs.

What language are you using?

Most languages have some sort of similar construct.

Share this post


Link to post
Share on other sites
Quote:
Original post by rip-off
Quote:
Original post by by
Well, i'm not using cpp for a long time :) I don't know about "std::vector". Can you tell me what is it? :))


A resizeable array that will expand to your needs.

What language are you using?

Most languages have some sort of similar construct.


Hmm, i get it thanks :) I am using C++.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Actually, there's probably nothing wrong with using an array big enough that the player won't reach the limit. This is, after all, what most commercial games do. As long as the limit is something reasonable. Commercial games seem to choose the limit based on what the game engine can reasonably handle on the target platform. You just need to handle the case where the player actually does hit the limit, or ensure the player doesn't hit the limit.

A C++ vector is just an automatically managed dynamic array. When you add elements to it, it automatically reallocates more memory. Such a system can also be used. But you'll probably run into limits other than memory if too many units are created, since updating all of those units takes time.

Share this post


Link to post
Share on other sites

This topic is 4302 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this