![]() |
Idea for maps - Printable Version +- Mirage Engine (https://mirage-engine.uk/forums) +-- Forum: Mirage Source (Nostalgia) (https://mirage-engine.uk/forums/forumdisplay.php?fid=61) +--- Forum: Archive (2006-2011) (https://mirage-engine.uk/forums/forumdisplay.php?fid=18) +---- Forum: General (https://mirage-engine.uk/forums/forumdisplay.php?fid=17) +---- Thread: Idea for maps (/showthread.php?tid=1496) |
Idea for maps - Psychoboy - 09-01-2008 I havnt seen a real solution for this issue anywhere. Someone may have a better idea then this. Issue: Large maps or lot's of players online requesting maps causes lag spikes Possible Solution: My idea for a solution would be instead of having the server send a large packet or recieve a large packet. Why not direct file transfer? The bigger issue is VB6 doesnt support multi-threading so processing all the data is a bit of an issue. Any other recommendations for a solution or something for this I am open for discussion on. Another solution could be possibly breaking up the packet into many packets to give the server time to process other information in between Re: Idea for maps - Spodi - 09-01-2008 Use binary (or if you're feeling real badass, bit) packets instead of string packets and don't send such a needlessly huge set of data? My opinion - don't worry about it. If you want performance out of Mirage, you'll never get around to making your own game. Make the game first, and if that doesn't fail, then worry about performance. Re: Idea for maps - Psychoboy - 09-01-2008 Spodi Wrote:Use binary (or if you're feeling real badass, bit) packets instead of string packets and don't send such a needlessly huge set of data? I have already made a few successful games. My solution then was just releasing updates with the maps instead of doing maps on the fly. Either way packets would be large. The maps eve in binary are still about 64kb. Sending those out would still cause lag. Dave Wrote:Store the maps and data files client side?I've done that before but does not solve the solution of being able to update maps on the fly. Re: Idea for maps - Psychoboy - 09-01-2008 Dave Wrote:So update them on the fly and store them client side. Currently Mirage checks the revision, and regardless if it's the same or not, it updates. Just fix that system and problem solved. I think your mis-understanding the whole idea here. The idea is to update maps on the fly. I.E. for player housing. the issue is when it updates them it lags. and thats where I am trying to come up with a solution for and thats why I posted two potential idea's to get others input on it. Re: Idea for maps - Spodi - 09-01-2008 64KB when stored poorly, maybe. Theres no way that is the smallest the files are if you do things properly. In fact, if you use optimal binary, they will most likely all be different sizes. 64 KB is still quite large for a map containing nothing more than a few graphics and a very small, static size. As Dave said, if you're updating them, all you need is a revision number. When you check to update the map, check if the revision number is different - if it is, update it. If not, don't update. Re: Idea for maps - Psychoboy - 09-01-2008 Spodi Wrote:64KB when stored poorly, maybe. Theres no way that is the smallest the files are if you do things properly. In fact, if you use optimal binary, they will most likely all be different sizes. 64 KB is still quite large for a map containing nothing more than a few graphics and a very small, static size. 64kb is probably worse case. but you guys are missing the whole issue. I know how the update system works with the revision and such. The issue is maps are large packets. VB6 cant multi-thread so while its sending this large packet it lags the whole server because it cant process anything else. Re: Idea for maps - Spodi - 09-01-2008 We're not missing the point. Shrink the map size. Simple as that. Looking at the default MS 3.0.3 maps, its just raw memory storage, which is as fast as it gets but probably as large as it gets. And still, this is only 3 KBs. Re: Idea for maps - Spodi - 09-01-2008 Alright, here you go. Some basic enhanced encoding of the tiles. I could have done better if I had my other tools like my bit stream or knew more information about the data, but this is good enough. Code: Sub SaveMapSpodi(ByVal MapNum As Long) I lacked the give-a-shit to actually test it with some real maps or to do the decoding, but its pretty simple. The header is quite basic and explanatory. The tile system I used two different encoding techniques on, first being the same as the header's, second being a recursive updated library. A little explanation: Dynamic non-guessable variable bit flags: This is what the first tile encoding and header uses. It holds a bit for every variable. If the variable does not equal the default value (I just used 0 for everything since I have no idea what the common values for them are), it has to be written. A 1 in the bit states the value was written, while a 0 states it was not. This allows us to eliminate having to write any value that is equal to the default, and provides us a foundation of understanding for the next method... Recursive non-guessable variable bit flags: This is the same as above, where a value is written when we can not 100% guess the value. But unlike above, instead of using a constant dictionary (in my example, it was just all 0's) for assumed values, we use a dynamic dictionary, where the assumed values are equal to that of the previous tile. The bit flag meaning changes a little bit, but the output is still the same. The values we are writing out are what is different from the dynamic diction, resulting in a recursive updating. For example, if we had the theoretical data set {A, B, C} and we wanted to write {A, B, D}, we would write the bits 001 stating that A and B were equal, but C was not, then we would write D out so we know what to replace C with. When decoding, we'd just update the dictionary then the dictionary would now be equal to the tile. Some of you may be now thinking, "Well Spodi, what if I made it smarter at guessing? Could I theoretically make the map take up less than, say, 10 bytes?" Yup. Totally plausible. The catch is that you have to be able to guess it. The recursive updating I used just assumes that the last tile will be somewhat close to the current tile. Seeing as that this scans on a horizontal line left to right, vertical top to bottom, the tiles will vary a bit since a tile often has similarities to other tiles near it, so this is far from optimal. Most likely you will never be able to get such accurate guessing in less than 10 bytes of data unless your map is very predictable, but you can make it take a lot less than I have had it use up. The results: Now for the interesting part - the results. Like I said earlier, lacked the give-a-shit to do much more than the basics or to test this on anything but the auto-generated maps, but these took up 218 bytes while the default maps took up 2925 bytes per map, resulting in a file 13.5x less than the original size. Sounds good enough to me. You'll actually be able to fit that whole map into a single packet. Hell, you can fit almost 7 maps into a single packet. How to improve: Like I said earlier, one way to improve things would be to improve the guessing system. Though unfortunately, besides altering the order of tiles it reads to a more optimal approach such as crawling the tiles from a center point and reading outwards in a node-based system, using the parent node to retrieve the source dictionary to allow for less variation from the dictionary, guessing is pretty much at a peak on a algorithmic standpoint. You could devise a routine to read all your maps, create a dictionary that holds the percent change of finding tile X when surrounded by tiles A, B, C, D, E, F, G, and H, but that would require quite a bit of effort. In the end its just not worth it except for extreme cases. Another improvement would be smashing down those goddamn bit flag sizes. How might we do this? Professor David A. Huffman may have an idea. Huffman encoding is a variable-length entropy encoding using a weighted binary tree generated by the Huffman algorithm (yes, the encoding and algorithm are different things, but the encoding is just the application of the algorithm). Its a very simple encoding algorithm, but it is going to require a bit stream to make use of. This will work on randomly placed sets of values as long as we know the start of the value because Huffman encoding has a definitive end-point. When you crawl the tree, you always hit the end (unless you **** up something), and you just read until you hit the end. It is practically a given you won't use up every one of the 256 different bit combinations for the tile bit flags. In fact, you'll probably be using around 20 or so at most. How you would do this is go through as normal and generate all the bit flags for the tiles, but instead of writing them out, you will store them in an array. This is your first pass. Generate a binary tree with the Huffman algorithm out of this. Write out a sequence of bits to generate the binary tree from so the decoder can understand the values. On the second pass, you will go through the exact same (though won't have to regenerate the bit flags again if you stored them in an ordered fashion), but instead of storing the bit flags, you will write out the Huffman encoding for that series of bits. Then just write out the other values as normal. Optimally, you'll be using probably around 1.5-2.5 bits per tile header instead of 8 (depends on how much variation there is). If so, that'd be about an extra 300%+ compression for the default map size. I won't bother elaborating since I doubt anyone cares enough to do this. I obviously had nothing to do this morning... and this probably would've been best in the knowledge base. Re: Idea for maps - Robin - 09-01-2008 Spodi Wrote:Alright, here you go. Some basic enhanced encoding of the tiles. I could have done better if I had my other tools like my bit stream or knew more information about the data, but this is good enough. I think I just creamed myself. Re: Idea for maps - Zalos - 06-02-2008 I hate to say it but I know what Psychoboy means by your missing the point He asked for a discussion of ways to go about to do it and maybe Ideas of what to do. You posted on How To Do It with out a discussion of which way is best straight out Use binary and shrink map size. thats not a discussion thats a statement, Most people who are trying to find solutions to problems learn best by a discussion strike up a conversation of possible ways one tends to learn more, or get a light ball of how to do it, that way they can learn from it. Spodi may feel his way is best thats great but did you take time to discuss why its best or maybe the pro and cons of other possible solutions? Not really. so in seeking a conversation from which other people could and read to learn from everyone got a do it like this because I say to. and Yes I know the last post was Quote:Posted: Wed Jan 09, 2008 8:57 pm However it could still be a good thread if you started discussing. EDIT: Psychoboy Wrote:thats where I am trying to come up with a solution for and thats why I posted two potential idea's to get others input on it. EDIT2: I went through and read spodi's huge Post, Great explanations of how to do things your way rather impressive as well mind if I see If I can do something with it? Re: Idea for maps - Spodi - 06-02-2008 What I wrote is a start for some stuff you could do to compress the data and I thought I made that pretty clear. You obviously don't have to do it my way. I provided an explanation along with code to go with it - I'm not sure what else I could give you. I don't think you really understand how things work with this case of data compression. Theres not really a "pro" or "con" to anything. It either results in smaller data or it doesn't. Only cons I can think of would be time and complexity and those should be pretty obvious just by looking at it. Theres not "method one" and "method two" and you get to decide which one you want to use, theres just hundreds of different techniques ranging in all sorts of depths and complexities and you have to mash them together to find out which would be optimal. Why do people say just "use binary instead"? Maybe because of the assumption that if you can't write out the binary yourself, or be able to ask specific questions on what you need help with instead of just "how do I make this data smaller?", its probably beyond your level already. Re: Idea for maps - Zalos - 06-02-2008 Spodi Wrote:What I wrote is a start for some stuff you could do to compress the data and I thought I made that pretty clear. You obviously don't have to do it my way. I provided an explanation along with code to go with it - I'm not sure what else I could give you. I don't think you really understand how things work with this case of data compression. Theres not really a "pro" or "con" to anything. It either results in smaller data or it doesn't. Only cons I can think of would be time and complexity and those should be pretty obvious just by looking at it. Theres not "method one" and "method two" and you get to decide which one you want to use, theres just hundreds of different techniques ranging in all sorts of depths and complexities and you have to mash them together to find out which would be optimal. LOL, Yes in my post I will admit I editted it while you were prolly posting this, since I went through and took the time to read your explanations however to go straight out and say Its probably beyond your level already, with knowing next to nothing about me tells me alot about yourself, very assumptive. I now see why he decided not to waste his time posting here. Re: Idea for maps - Anthony - 06-02-2008 Wow, I missed this before... Hey Spodi, would you mind shedding a bit of light on how to do the decoding? Re: Idea for maps - Spodi - 06-02-2008 Zalos Wrote:however to go straight out and say Its probably beyond your level already, with knowing next to nothing about me tells me alot about yourself, very assumptive Actually I was saying that if you have no idea where to even begin when it comes to shrinking the map's size by using binary that it is beyond your level. I was not saying you yourself, but just you the reader. That would be like trying to optimize your code by doing some in-line assembly without even knowing assembly. Zalos Wrote:I went through and read spodi's huge Post, Great explanations of how to do things your way rather impressive as well mind if I see If I can do something with it? Of course, thats what its there for. ![]() Vegeta Wrote:Hey Spodi, would you mind shedding a bit of light on how to do the decoding? Sure. First just grab the name and revision as those will always be there in that order. Next grab the HeaderBitFlags integer. Then, in order, check if a bit is set and if it is, grab the bit for that value. It'll look a lot like how it is already for the output but using Get instead of Put: Code: If HeaderBitFlags And 1 Then Get #f, , .Moral Now for the harder part. Initialize the LastTile values to the defaults (vital they're the same defaults as the encoder) then make a For loop just like above for the tiles. Then grab the TileBitFlags byte. Read the bits just like you wrote them, but you also have to add an "Else" for when the bit is not set which tells you it is going to be equal to the LastTile value. It'll look something kinda like this: Code: LastTile.Anim = 0 The resemblance to the encoder is very strong as you can see. For the most part theres just the Put being changed to Get. Re: Idea for maps - Zalos - 06-02-2008 Spodi Wrote:Zalos Wrote:however to go straight out and say Its probably beyond your level already, with knowing next to nothing about me tells me alot about yourself, very assumptive Well sir then I owe you an apology I thought you ment in responce to my post. Which was very assumptive myself. ;-) Zyrius Re: Idea for maps - Anthony - 06-02-2008 Thanks Spodi, this is such a great bit of code, I work all week and have almost no time but I will try it out as soon as I can and hopefully can get it working. Re: Idea for maps - Spodi - 06-02-2008 Zalos Wrote:Well sir then I owe you an apology I thought you ment in responce to my post. Which was very assumptive myself. No problem, was just a small misunderstanding. ![]() Vegeta Wrote:Thanks Spodi, this is such a great bit of code, I work all week and have almost no time but I will try it out as soon as I can and hopefully can get it working. Glad to help. ![]() Re: Idea for maps - grimsk8ter11 - 19-04-2008 Psychoboy Wrote:The bigger issue is VB6 doesnt support multi-threading so processing all the data is a bit of an issue. i know this is a necro post, but i thought this to be relevant vb6 does support multithreading quite well: http://www.freevbcode.com/ShowCode.Asp?ID=1287 Re: Idea for maps - Spodi - 19-04-2008 Even if you get multithreading working in VB6, it is very poor. For one, the IDE does not support it so it will make debugging hell. vbGORE, for instance, if you just press the stop button, it can crash the whole IDE since GOREsock uses subthreading. VB6 also completely lacks the kind of debugging tools of modern debuggers like stack views and telling threads apart. Re: Idea for maps - Tony - 22-04-2008 This is why attempting to make a game is so scary. I understand nothing. Re: Idea for maps - Robin - 22-04-2008 This isn't making a game, this is making an engine which allows you to make a game. Re: Idea for maps - Anthony - 07-03-2009 I know this is old. Has anybody tried to get Spodis method working that he posted here? I have been messing around with it in a dynamic map system. With all 4 default layers filling a 100x100 map with attributes randomly placed around and all 5 npcs the default MS saving scheme saves the file as 153,063 bytes. But with Spodis bit of code here it's cut it down to 42,525 bytes. Which is quite good. I am having a problem with loading it though. The Npcs aren't loading when you first get warped to a map but it seems as if everything else is loading properly. When I open the map editor it's all there and when I click send the Npcs spawn and show up. Here is my loading sub. The saving one is almost exactly the same as the one Spodi posted before. I am using the independent tile encoding, not the delta. Code: Sub LoadMaps() Can anybody see anything that's incorrect here? Thanks guys. Re: Idea for maps - Anthony - 08-03-2009 I looked and everything seems normal. It's quite strange.. If I am on the map when the server is first loaded the npcs don't appear, if I respawn it warp to it or move off the map and back again they still wont appear. Only if I click send again in the map editor. Possibly something to do with the revision I thought but I looked into it and I can't see anything wrong there either. Also discovered if I send the map the npcs appear and I can log off of the client and back in and they will still be there as if everything were normal. But if I shut down the server and restart it then they won't be... Just was testing some things. Clearing the maps client side creates an almost random appearance of a tile in the top left corner (0,0) of the map. Usually it's black but sometimes it's a different tile haha. Which is double strange because I don't have any black tiles in the tileset.. Hmm. Then in the map editor it now says there are no Npcs on the map even though they were. This is my saving sub. Maybe I am definitely screwing something up here. Code: Sub SaveMap(ByVal MapNum As Long) Do I need to do this the same way for the client or can I leave it as it normally is? Might be a stupid question xD Re: Idea for maps - Matt - 08-03-2009 Pure curiosity, since I know you're using the same base as me. Client side, do you still have a "Do Events" in the savemap sub? Not sure if this is your problem, but it caused the same issue with me and my npcs. Re: Idea for maps - Anthony - 09-03-2009 Nope, it was removed before I added this. |