zokum Posted October 29, 2020 This is something I will most likely code myself, sooner or later. Most likely later, so I figured I'd leave up some pseudo code for people to comment and suggest on. Maybe I have overlooked something obvious. The point of the algorithm is to be easy to write, correct and as little complexity as possible. One important aspect is the idea of writing to an intermediary format that makes changes and optimizations easy to perform, and then as a final step convert it to the correct DOOM format. I will attempt to make it into a really fast algorithm that quickly produces a working blockmap, and only compresses if there's an actual need. On modern hardware this is somewhat pointless for small maps, as compressing them still wouldn't take long. The new idea with this blockmap is that a blockmap can be compressed a lot better that with older algorithms, and that reaching close to a size of 65536 bytes no longer means you have to 'stop adding' to the map in order to avoid crashes. If I am unclear or leave out something that should be in there, please tell me, and I'll try to explain it in a post and update the pseudo code. ---- The blockmap consists of 3 parts. The header, the grid and the lists. The header is always fixed in size. The grid varies in size depending on the span of the map geometry. The lists contains a list of all the lists found in one or more blockmap grids. We compute the size of the final blockmap and then work on the most promising candidate if we have multiple, and the compress it until it can be stored in the wad in the final DOOM format. The size is at least the blockmap header + grid data size. If this size is below 65534 (2^16 -2) a valid blockmap can be constructed, so continue. # Lists are a bunch of linedefs that exist in one or more areas, there can also be sub-lists. What a sub-list is, will be explained. Generate lists for all the grid cells. Put them into a linked list and sorted smallest list first, insertion sort when new lists are added. Each grid element contains a pointer/reference to the linked list entry + an integer that specifies which bu list to point to. Sub list number is always 0 at this stage. Whenever a new list entry is added, compute how big that list will be in DOOM format (header + linedefs + end marker). Add this to the list entry and add it to the total size of the final blockmap in DOOM format (header + grid data + lists). The header can be ommitted as most modern ports and doom2.exe does not require it. This header should be optional to ommit, on by default due to zdaemon etc. Go through the list, find the size of the longest list, and compute the maximum size of a DOOM compatible blockmap as 65534 + the size of the biggest list (the last entry). # The last list can have data over the 65536 byte limit. Only the header/first linedef has to be within the 65536 data space. If the final format is small enough, convert it to DOOM format and we're done. If the blockmap is too large, start by looking at the smallest lists. See if there are other list entries that are identical to this one. Update the entries in the grid so that they now point to the new "compressed" entry. Typically the smallest entry will be the grid cells that contain no linedefs. Typically outside the map and inside big open areas. Care should be taken to ensure that the computed final DOOM size is updated at each compression. # By handling the empty lists in this manner, no special code is needed to handle these. Empty grid cells are treated just like any other cells. As soon as an entry has been compared to all others in the list compute the new final size, if it is small enough, we're done with the blockmap and can convert to DOOM format. #Since lists are sorted by size, one does not need to check lists that are longer, making it really fast to compress all the lists. Repeat this step for every list but the last one, checking only for the ones longer down in the list. # If list entry 15 isn't identical to the later list 17, there is no point in later checking if 15 is identical to 17. #If all of the lists have been checked and compressed against eachother and we're still at a final size bigger than the biggest possible size, we need to do another round of compression with a more aggressive strategy. Start at list entry 0 again and try to find another list where the first list is a sub list. We'll then compute a score to decide which lists to "merge". (We can skip checking all lists that are the same size.) # List 0 will always be the one with no lindefs in it, if they exist (most maps have them, apart from size-restricted maps). Thus no linedefs will always be a sub list of all other lists in the list. # This metric may not be the best, other metrics might be better, please suggest. Once a list is found to be a sublist, the metric is the amount of times the bigger list is referenced from a grad times the size of it. # If 123 is a sub-list of 123456 and 123456 is referenced twice in the grid, the final score is 12. Whatever ends up as the lowest metric, we use to perform a merge of lists. The cruicial difference with this merge is that the smaller list is added as a sublist to the bigger list. # Merging 123 into 123456 will give use a list entry of 456 with a sub list of 123. Merging 129 into 123456789 would give us a list of 345678 with a sublist of 129. We perform these merges until we are below the magic size goal OR we have change to an even more aggressive compression algorithm. When a grid points to a sublist (counter other than 0) care must be taken when writing the final DOOM format. # Two separate lists (123 and 123456) should look like this: #0000 0001 0002 0003 FFFF (10 bytes of data) #0000 0001 0002 0003 0004 0005 0006 FFFF (16 bytes of data) # 26 bytes of data in total. #Merged they should end up as # 0000 0004 0005 0006 0000 0001 0002 0003 0004 FF FF (18 bytes of data, notr the two 00 000 headers, but only one end marker). The DOOM format grid entries should point to the correct header, at the start for list 0 and at the second 00 00 entry for the first sublist. # Once this has been done for all the lists apart from the last one, as the last one cannot be a sublist of any other, and we still aren't below the magic size we need, we will have to merge more aggressively. Do another set of merges, starting at list entry 0, but this time look for two lists that have many linedefs in common, since none of the lists are sublists as all of those have already been found. # This metric is just a suggestion, due to map complexity and design no perfect metric can be found. Compute a merge score for each list based on the amount of elements not in common in each list times the times each list is referenced. # 1234 and 23456 would be quite good merge candidates. We could end up with a final list of list: 1, sublist 23456. This would mean that when the games performs collission checks on what used to point to 1234 it would check on just that, but on 561234 + extra header for the list that used to point to 23456. Redundant checks are common in Doom due to a bug in id's tools and most tools designed to mimic id. # To sum it up # Checks for the other list would start at sublist 1 and not have any overhead. # Care should be taken as to which of the two lists should be the ideal check ( the sublist). Without going into too much detail, the rest of the algorithm would simply be to merge the lists until you're done compressing the data enough. The worst case scenario would be ending up with every list merged into one big list. That would happen with an enormous map area, leaving almost no room for list data. One possible compression technique would be to merge sublists into fewer sublists or into the main list, to remove header overhead. This reduces size at the cost of adding redundant checks at run-time in more cases. Exactly when to use this technique is an open question, but it should be used for lists with many sublists. # For instance a three sublist list of lindefes 1,2,3 and 3 headers: # 00 00 00 01 00 00 00 02 00 00 00 00 03 FF FF # Could merge into # 00 00 00 01 00 02 00 00 00 03 FF ---- With this approach outlined here, you could easily have DOOM compliant blocklists in excess of the conventional 65k limit and a great deal more map data than was previously thought possible. Be aware that the game speed would suffer with many merged lists due to many pointless linedef checks. This also incrases the chance for errors in collission detection due to the bad algorithms in DOOM. However the computation speed in modern CPUs most likely make the speed issues less noticable. More wonky collission detection is a bigger problem. However since practically all blockmap lists in the IWADS and PWADS use the 00 00 header which by the engine gets treated as a reference to linedef 0, this possibly buggy behaviour happens for every single blocklist test in the game. Ommitting the 00 00 header makes the compression a lot more efficient and greatly reduces overhead. A list of 1,2 with sub list 3: 00 00 00 01 00 02 00 00 00 03 FF FF This becomes: 00 01 00 02 00 03 FF FF. This is a saving of 4 bytes, so from 12 to 8 bytes, a nice 33% size reduction AND better collission detection. A higher number of sublists means more overhead. Unofrtunatly the last time I tested not all ports had reverted the bad BOOM fix. Zdaemon didn't work correctly without redundant 00 headers. BOOM and some other ports will assume the first entry in a list is a 00 00 header and skip it, making collission detection fail for the first linedef. Of note should also be to test different offsets for the list data and try to compress the lists that gave us the smallest set of list data. This is done in ZokumBSP and is a different optimization level before the list compression stage. I was kinda tired when I wrote this algorithm and it ended up being a lot more complex to explain than originally envisioned, but I figured I'd share this with the community to get some feedback and ideas before someone else or myself start coding it. 4 Share this post Link to post
