I'm not actually editing anything, but I've had this idea for a while that I thought I should get out.

Basically, I've been wondering if you could have a plugin for JED/ZED which takes a level and optimizes all the sectors and surfaces to minimize triangles and adjoins (I know we have a hack round the adjoin limit, but anyway...).

My idea is that you would merge all the sectors and then automagically cleave them in such a way that you ended up with valid sectors. Except the magic bit is that this is pseudorandom, you generate a bunch of possible solutions and see which ones are best and you mix them.

Summary: a genetic algorithm for optimizing levels in games.

Don't you mean:

Summary: a genetic algorithm for optimizing levels in games no one plays anymore

Sure, but this would do me wonders. I'm terrible for having unorganized and useless cleaves/adjoins.

I'm just the opposite. I try as hard as I can to make sure everything is as efficient as possible. I would be extremely surprised if an algorithm like that could improve it. Then people would run the lighter plugin and they'd all get messed up again anyway.

You may get better results if you just go through the level and merge sectors in random orders (as opposed to merging then cleaving) -- run the equiv. of the consistency checker and reject if it causes an error. This would be easier too as you could prequalify sectors (only try where they're already adjoined).

Oh yeah, you'd have to be careful about messing up any adjoin/surface/geo tags when doing this. For example, with water, you *can* merge the sectors, but then you couldn't get the water texture between the water and the sky.

So... generational BSP?

Pretty much, I'm just curious as to how effective it could be.

I do have a few thoughts:

1.) Your fitness criteria are suspect. A minimal number of surfaces or adjoins will not necessarily yield the highest performance, if that's your goal.

Consider the following situation: The level designer has created a detailed hallway segment with pillars. His original work has 20 adjoins (denoted by *s):



Now you run it by your algorithm, which reduces the total number of adjoins to 16:



In most typical cases, the player is in the middle of the hallway proceeding straight ahead. With the original suboptimal solution the player has to look through 4 adjoins; the optimized solution doubles it to 8.

This is just an example. I'm sure someone else can come up with something that makes it really explode.

2.) This is superficially similar to BSP, which is really just a process of imposing the sort of structure on polygon soup that JK levels already have. I think you'd be shooting yourself in the foot if you started off by eliminating that structure.

3.) This is one of those hard problems that tend to show up in a lot of places.

I'm not sure what you mean here. Determining convexity is the biggest non-problem in this idea.

I've minimized visible adjoins in highly detailed areas where I know the player isn't or doesn't need access to by merging sectors that yielded non-convex sectors.

Similar to what Brain suggested, it would be nice if ZED warned you after you hit the Merge button that it will produce a non-convex sector and give you a chance to cancel. I don't want it to reject it, I want the option to cancel or proceed anyway. This wouldn't be that bad if after you merged sectors, realized they were non-convex and hit the undo button, that some of the sectors are deleted...

Yeah JED's undo is a pile of ****

Undo is really easy to implement if you have a good MVC.

JED doesn't have a good MVC.

This deserves more discussion.