Tuesday, April 17, 2012

Deck Editor and Schlemiel’s Algorithm

Years ago I wrote Forge’s first deck editor. It didn’t do anything fancy and you couldn’t search for anything. You really didn’t need to “search” much because Forge only had a couple hundred cards. I did work hard on the deck editor’s “sort” feature which let you sort cards by name, type (instant, creature, etc…), mana cost, power or toughness. (In my mind “sort” was good enough, so a separate search function wasn’t really needed.)

(From the upcoming set Avacyn Restored)

But there was a problem. As more cards were added, the deck editor’s sort function became slower and slower. At first I guessed that it was a problem with Java but it wasn’t. I thought I was implementing “sort” correctly and that was as fast as it could be. (Later, I learned the correct way to sort things using Java’s JTable.) This “slow sort” problem plagued Forge for a couple of years until the nice developers totally revamped the deck editor and now it is awesome. The new deck editor is actually fun to use because it works so well.

The old deck editor basically used a “n squared” solution that grows very quickly. For example, to sort 100 cards it might take 2 seconds, 200 cards - 10 seconds. But to sort 300 cards took 15 seconds. As you can see, the sort times grows fast very rapidly. For a funny explanation of the same thing, real Joel Spolsky’s explanation of Shlemiel the painter below.

(Begin Quote)

Shlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. "That's pretty good!" says his boss, "you're a fast worker!" and pays him a kopeck.

The next day Shlemiel only gets 150 yards done. "Well, that's not nearly as good as yesterday, but you're still a fast worker. 150 yards is respectable," and pays him a kopeck.

The next day Shlemiel paints 30 yards of the road. "Only 30!" shouts his boss. "That's unacceptable! On the first day you did ten times that much work! What's going on?"

"I can't help it," says Shlemiel. "Every day I get farther and farther away from the paint can!"

(End Quote)

Basically it is hard to know if you have the “right solution” when you code. A program can be fine until you add that one feature that just breaks everything. Life and computer programming are both comprises. The perfect solution does not exist.

Excelsior,
mtgrares

p.s.
Joel Spolsky is great and each article has more computer info than my 4 years in college studying computers. Read his blog and be enlightened. For those people who can follow some short code segments in C, Joel talks more about C and Shlemiel here.

Joel Spolsky’s book’s “Joel on Software” and “More Joel on Software” are the best things that I have ever read. They are more readable (and edited) than his blog.

Joel Spolsky’s Blog

4 comments:

Mr. Markov said...

Question: Can you create the option to play EDH? The current version allows for neither Generals, not the Alternate general dam,age win con, and it starts at 20 life instead of the 40 for EDH.

Anonymous said...

yeah, the first solution is not always the most efficient one. There are many algorithms especially for searching and sorting and there are many data structures like lists and trees and stuff to improve data access just by another inch.
Have a look at the following free book: http://opendatastructures.org/
or look at books from Sedgewick, Knuth, Mehlhorn, etc.
It would be nice to know, in which structure you represent all those cards; if it is a vector, I bet it is pretty much inefficient and a tree or skiplist will be much faster.

Doublestrike said...

@Mr. Markov - a new game mode is a somewhat significant time investment. There's a lot on the table already that we'd all love to implement, but in all honesty there's no one working on new game modes right now.

Currently most of the focus in the codebase is on finalizing the script system to handle the massive amount of cards/abilities, unifying the UI, and putting better standards in the code. Oh, and the spoilers too :)

I think I can speak for all of the devs when I say we'd love to see more game modes too, but we're just focusing on different stuff...the worm will turn and there'll be something new (maybe this year?), but for now there's nothing planned.

Agro said...

@Mr. Markov - EDH can be kind of done by using the developer menu (not available in the current version, but definitely present on older versions <1.2 I think) to set your life total to 40, and then tutor for your general when you want to cast it. General damage can also be tracked with counters on some permanent