27 Aug, 2013, Davenge wrote in the 1st comment:
Votes: 0
So, I'll be converting my muds resets to be handled individually as opposed to globally by area. I will also be converting to an event system similar to the one written in Dystopia 2.0 but with my own original code and design.

My event system will handle events in a queue based on seconds and then quarters seconds.

The event queue system will look something like this:

MAX_SECONDS = 62
MAX_PULSE_PER_SECOND = 4

event_queue[MAX_SECONDS][MAX_PULSE_PER_SECOND];

event_queue{
EVENT_QUEUE *next;
EVENT_QUEUE *prev;
time_t event_time;
void *event;
int type;
etc etc etc;
};


Now, I could put the resets into this queue, that wouldn't be much of a problem. But, then I thought of an alternative method that would processor wise be even faster but potentially hog more memory resources.

respawn_queue respawn_table[MAX_MONTH][MAX_DAY][MAX_HOUR][MAX_MINUTE][MAX_SECOND];

struct respawn_queue
{
respawn_queue *next;
int vnum;
};



Everytime a second passes. It will put in corresponding data from ctime/time.h struct tm into the array and if its not NULL, spawn all the vnums to that linked list.

So, basically, which is better? Does it really matter? Incorporating resets into the event queue will amp up its processor usage but the large respawn_table array takes virtuaully no processing power but potentially hogs a lot of memory. Especially since 99% of the respawn_table will be empty. Now, I do plan to have many mobs that take days to respawn, so a single respawn could add an extra but of usage onto the event_queue for days. But, it shouldn't bog it down that much? I dunno, I just thought about it. I'm only really doing this because its cool, I could just brute force it with one large linked list that just cycles every second. But, I'm tryingn to get away from that sort of coding.

Feel free to weigh in.
28 Aug, 2013, plamzi wrote in the 2nd comment:
Votes: 0
Not a guru and I can't pretend that I read and understood everything, but I have some quick comments:

* Do you really need to go down to the second for reset events? If you don't have stuff respawning multiple times per minute, down to the minute should be enough?

* If you're really going to go up to day and even month, what about persistence? If your server is not rock-stable, restarts and crashes would be upsetting your game balance.
28 Aug, 2013, Davenge wrote in the 3rd comment:
Votes: 0
I do want them to be that accurate because I want players to be able to set timers if multiple people are competing for one spawn. Also, with the event system, some combat stuff comes down to quarter seconds. Same, with some of my AI stuff.

To the second, it will read out when it is created and deleted when it is used. However, there's a hybrid system after doing some math on the memory usage with a friend.

Of simply expanding:
event_queue[MAX_HOURS][MAX_MINUTES][MAX_SECONDS][MAX_PULSE_PER_SECOND]


The array will only take up .33 megabytes of ram full of pointers as opposed to that super long int array that even if converted to pointers and fully NULL allocated would take up 30 megabytes of ram which I just don't have. Especially since those pointers would be pointing to things using ram as well. I've decided to go with this because its basically a hybrid between the two. Just a little harder on the processor when compared to the Memory Option route but way gentler on ram usage.
28 Aug, 2013, Runter wrote in the 4th comment:
Votes: 0
There's no reason you can't have it down to the second. And I tend to agree that a minute granularity is much too big.

I'll sum up a really easy way to implement this.

Basically keep a sorted container containing structures that have a date data, and the reset data.

Iterating over each item in the container and reducing a "countdown" would be a terrible a way to implement this.

A much more sensible way is to check the very first entry in the container. Since it's sorted, we know that if the current time hasn't passed the time on this element, we don't need to do anything else.

logic can be like this:

loop do 
r = arr.shift()
if r.reset_at_this_time < current_time
do_reset(r.reset_data)
else
break
end
end


So, my advice is focus on the timer part of it first. Encapsulate it so that you can set arbitrary future times and have code fire once the timer is up. Then just build your reset system into it.
28 Aug, 2013, plamzi wrote in the 5th comment:
Votes: 0
Runter said:
So, my advice is focus on the timer part of it first. Encapsulate it so that you can set arbitrary future times and have code fire once the timer is up. Then just build your reset system into it.


It's even easier to implement this if you're saving to a db table. Query returns all the timestamps that are pending. And, you get persistence.

I have no idea what you mean by "because I want players to be able to set timers if multiple people are competing for one spawn." I'm going to assume it's something crucial to the success of the game :)
28 Aug, 2013, quixadhal wrote in the 6th comment:
Votes: 0
Why do you need to make this a multi-dimensional array?

It's far simpler to just have a "fast" and a "slow" queue, sorted by pending execution times.

If an item is going to happen in < 10 seconds, put it in the fast queue. When inserting, place it in the correct position. When executing, simply pop the top event and do it, and if recurring, re-insert it at the correct location again.

Why two queues? Because there's no point in looking at future events in the "slow" queue every time you spin through your game loop. Every 5 to 10 seconds, pull any pending events in the slow queue and push them into the fast queue for more precise execution.
28 Aug, 2013, Davenge wrote in the 7th comment:
Votes: 0
The only problem I have with Runter's system, besides the fact that its smart and I didn't think of it. Is…, its hard to track split second things this way. However, I could remedy this with Quix's fast queue and slow queue idea. Put the stuff that needs to be down to the split second, like combat/cooldowns/buff durations, stuff that's generally under a minute to begin with and then Runters for anything longer.

This is good stuff, thanks everyone. Further ideas, improvements, comments, welcome.
28 Aug, 2013, Runter wrote in the 8th comment:
Votes: 0
Dunno why you think what I proposed isn't fit for short lived things. It has a granularity down to the microsecond.

And re plamzi's suggestion, I agree a database would be an effective way to manage the data.
28 Aug, 2013, Tyche wrote in the 9th comment:
Votes: 0
28 Aug, 2013, Rarva.Riendf wrote in the 10th comment:
Votes: 0
http://www.mudbytes.net/file-497

Would not this work for you ?
28 Aug, 2013, Davenge wrote in the 11th comment:
Votes: 0
Runter, the only reason I thought this was because I was planning to use time.h and I don't believe it tracks down to the micro-second, but I could be wrong.
28 Aug, 2013, Davenge wrote in the 12th comment:
Votes: 0
Rarva, I already run a system more or less like that for combat, cooldowns, buff durations, etc. The problem is, those things aren't a big deal if the mud comes down. They can just be requeued when the player logs back in. But for a player trying to time a spawn over a 24-72 hour period. If it spawns late because the mud went down and I hadn't wrote out where the delay was at recently, its spawn time would be off. You're right in this is the sort of thing I'm looking for, but I think I can do better. And, since I don't use any databasing stuff, I write to flat text. Now, I could write out everytime I decreased the delay, but that would happen 4 times a second. Doesn't really make sense to do that. By simply writing out the time once, and queueing it at that time in an array, it will only look to it once a day and the times will match it will execute the reset. If I save out the exact time an event is supposed to happen, it will always be accurate unless the mud is down at that specific time.

Now, you may just be saying, "why not just convert to SQL or something?" And maybe I will, but right now I don't want to have to learn SQL and in particular converting a muds read/write stuff to SQL. One day, sure, right now, my goal is to create a playable game that I can have fun with.

Tyche's priority queue one looks nice, but it seems you have to know the capacity of the Queue at the start. And maybe you could realloc a new queue if you needed to. But there could/can be anywhere from 1000-10000 events queued up in my mud depending on how many players are on, how many mobs are spawned, how many skills are on cooldown, how many affects are on players, how many fights are going on. It's just a shear mass amount of events.

That being said, Runter's looks like the best sort of solution, the only downside I have after the microsecond situation which apparently I don't need to worry about would be having to sort that maybe events. Obviously, you'd never have to sort it all at once, just when a new event is queued. But, tons of events could be queued every second and they'd need to be sorted. With the original system I proprosed, there's no sorting, you just stick it in at the beginning because it goes with all other events that need to go at its time. It may be skipped because the dates on the times don't match up, but it will only be looked at once a day.

You guys have been invaluable, showing me new ideas, and giving me things to think about and compare, thank you so much.
28 Aug, 2013, Rarva.Riendf wrote in the 13th comment:
Votes: 0
> If it spawns late because the mud went down and I hadn't wrote out where the delay was at recently, its spawn time would be off.

Whatever the method you use, if you don't save , it wont be loaded when player reconnect. I fail to see the difference.
And if your mud goes down, will the delay still be valid then ?

BTW if you mud goes down that frequently, I would look into fixing it first :)
28 Aug, 2013, Davenge wrote in the 14th comment:
Votes: 0
Hah, I mean, you have the right of it. Luckily it doesn't go down often. If it did, for whatever reason… It also doesn't have any players yet, hah.

My way I only need to write out when new events are added. If I save the delays to memory, I'll have to write out every time the delay is decremented. Which, could be 4 times a second. O_O
28 Aug, 2013, plamzi wrote in the 15th comment:
Votes: 0
Davenge said:
If I save the delays to memory, I'll have to write out every time the delay is decremented. Which, could be 4 times a second. O_O


I thought we were past that after Runter's extremely sensible suggestion.

If you're not looking to actually implement any feedback, but rather to get a confirmation that your initial ideas will work, then I think we can all agree that they will work (with all the caveats we've been listing).
28 Aug, 2013, Davenge wrote in the 16th comment:
Votes: 0
My initial post was to see which of my two techniques was better. And yes, Runter's is very sensible and I like it, I just don't like the absurd amount of sorting that would have to take place. When he first mentioned it, I was like duh! And normally it would be a "duh" situation. But, my mob in particular will have anywhere from 1,000 - 10,000 events queued up at any moment and having to run through that list to sort every time something is added doesnt seem to actually cut down much time. If I just go with a more hybrid of my two initial ideas, it would seem I gain a happy medium between processor use and memory use. That's all. I could be completely wrong. I may try a few different setups.

Right now, it's just fun for me to talk about this stuff. I didn't mean to ruffle feathers by not planning on using the feedback immediately. In fact, I have learned a lot from this conversation.

Sorry
28 Aug, 2013, plamzi wrote in the 17th comment:
Votes: 0
Davenge said:
And yes, Runter's is very sensible and I like it, I just don't like the absurd amount of sorting that would have to take place.


Even if you only keep the queue in memory, there's no absurd amount of sorting going on. When you're inserting, you'll just be looking for the right place to insert. That way, the queue is always sorted. And, in a db table, you won't need to worry about sorting at all.

What would be absurd, I feel, is the amount of decrementing you'll have to do under your initial plan. At least I hope you implement quix's advice to have a fast queue that's separate from the slow one.
28 Aug, 2013, Davenge wrote in the 18th comment:
Votes: 0
My initial plan? Like the one I have coded or one of the two I was asking opinions on?

Because the two I talked about have absolutely no decrementing.

The two I brought up originally you'd simply put at the front of their respective places in the array. With Runter's suggestions, I will have to find where each event fits into the queue. IE, each time I insert I will have to go down the list until it gets to its intended spot. And that list could be 1000s of links long. I don't typically know how fast this process is, so maybe my caring about this part is overblown, I admit that it might be. But, potentially going down that list thousands of times per seconds seems like it would take some power. With my system, it inherently knows where to place the event in the list based on the current time + the respawn time.

My current plan: organizing a 4 dimension array hash, I do no incrementing and only navigate the array with the current time being my location in the array and my pulse count. If that position in the ARRAY is not NULL, it will look at the list located and if time_t of any of the events on the list is greater than or equal to(which most of the time they should be equal because that is their location in the hash, unless they need to carry over into the next day) it will execute. No sorting required. Hardly any processing power, it just takes up memory. But the memory in question, even if all the pointers are allocated in the entire array will only take up .33 megabytes of ram. One way or another, all the events will have to be allocated so I'm not really worrying about their memory consumption, only the consumption of the physical array of pointers itself. If I was using a databasing system, I wouldn't even need to worry about that memory and only be concerned with the pointers if I was using a some good databasing software, but I'm not.

I may certainly do a fast queue for things that work on split seconds and a slow queue for separate things.

Look, for me, the planning stage is fun, which is why I brought it up here to get these sorts of inputs. However, I'm getting that you seem frustrated with me and that upsets me and that is not my goal. I'm trying to have fun, and talking helps me work through my own processes. It also helps me learn new things, you all have helped me learn more about this process from sharing those links as well as giving your own ideas and giving me other things to think about and consider. For which, I am grateful.
28 Aug, 2013, quixadhal wrote in the 19th comment:
Votes: 0
Davenge said:
Tyche's priority queue one looks nice, but it seems you have to know the capacity of the Queue at the start. And maybe you could realloc a new queue if you needed to. But there could/can be anywhere from 1000-10000 events queued up in my mud depending on how many players are on, how many mobs are spawned, how many skills are on cooldown, how many affects are on players, how many fights are going on. It's just a shear mass amount of events.


Why would you think you need to know the capacity ahead of time? And what's with the "realloc" nonsense? You need to learn that there are other data structures beyond arrays.

Most priority queues are implemented using a heap for the underlying data structure. You could do it with lists, but insertion time in a list can be slow since you have to walk the list in order until you find the insertion point. A heap mitigates that, since in most cases you only walk a small fraction of the data nodes.

I know when all you have is a hammer, everything looks like a nail. But there are LOTS of tools out there, and just because the DikuMUD authors only understood arrays and lists, doesn't mean you can't learn to use other things. :)
28 Aug, 2013, Davenge wrote in the 20th comment:
Votes: 0
Because the code he shared required a capacity?

I will learn more about heaps. Thanks for the suggestion.
0.0/23