Search code examples
c++domoptimizationchess

Quickly selecting elements in the DOM

Background: For one of my university courses, I am making Chess. The GUI is already finished with hooks into a controller, all I have to do is implement the objects. Traditionally, I would just use native structures suited to each type of object, a stack for a move history (undo supported, but not redo), 2d array/vector for the board, etc. Part of the specification is that I have to load and save the game in a specialized XML format, so I am tempted to simply use a DOMDocument to store the game in its entirety. This would make loading and saving extremely easy if I have a library that implements the DOM load/save actions, because I no longer have to translate between the XML and my structures.

Problem: Speed. In all of the algorithms in chess, I have to do a lot of selecting by location.

XML Format (unchangeable):

<board>
        <piece type="rook" color="white" column="0" row="7"/>
        <piece type="knight" color="white" column="1" row="7"/>
        <piece type="bishop" color="white" column="2" row="7"/>
        <piece type="queen" color="white" column="3" row="7"/>
        <piece type="king" color="white" column="4" row="7"/>
        <piece type="bishop" color="white" column="5" row="7"/>
        <piece type="knight" color="white" column="6" row="7"/>
        <piece type="rook" color="white" column="7" row="7"/>
        <piece  color="white" column="3" row="6" type="pawn"/>
        <piece row="6" type="pawn" color="white" column="4" />
</board>

Now I have to get all piece elements and filter out the attributes, an O(n) operation. In an array/vector implementation, I can easily achieve an O(1) time, because it's simple indexing. The price of O(n) is just too high to pay, especially when detecting stalemate.

How would you improve the speed? I'm basically looking for ways index the DOM. I've had some ideas, but how would you solve this problem?

For reference, I'm developing in C++ and will probably use the Xerces library for XML, though I'm mainly looking for ideas, not actual code (though that would be helpful).

Solution

  • Because the board for chess has fixed dimensions, I opted to go with a 2D array of DOMNode pointers. It's very quick, and while it does add some code complexity, it works just fine.

    I do wish I knew of another way to do things.