A simulation device that determines collision between objects at each of a plurality of calculation timings about a plurality of objects that move in a virtual space over time, the simulation device being characterized by including: a complete binary tree creating section that, at each of the plurality of calculation timings, associates pieces of position information indicating positions of the objects in the virtual space at the calculation timing with leaves and creates a complete binary tree in which position information reflecting pieces of the position information of child nodes is associated with an internal node; and a node shuffling section that is configured to shuffle 2·2 n (n ≥ 1) child nodes regarding each group of 2 n nodes on a basis of the position information associated with each of the 2·2 n child nodes belonging to the 2 n nodes in each layer sequentially from an immediately-upper layer of a lowermost layer in the complete binary tree, wherein the position information indicating the position of the object is a region in which the object that corresponds is inscribed, and the node shuffling section is configured to shuffle the 2·2 n child nodes belonging to the 2 n nodes into combinations with which a numerical value indicating a size of the region of a parent node becomes small; and regarding each of a plurality of combination candidates obtained by shuffling the 2·2 n child nodes, the node shuffling section is configured to randomly change the numerical value indicating the size of the region of a parent node with the combination candidate, and the node shuffling section is configured to shuffle the child nodes about each pair of two nodes and to select the combination with which the sum of the randomly changed sizes of the region of a parent node is the smallest from the respective combination candidates, wherein collision determination between objects is carried out by using the complete binary tree resulting from the shuffling by the node shuffling section. a complete binary tree creating section that, at each of the plurality of calculation timings, associates pieces of position information indicating positions of the objects in the virtual space at the calculation timing with leaves and creates a complete binary tree in which position information reflecting pieces of the position information of child nodes is associated with an internal node; and a node shuffling section that is configured to shuffle 2·2 n (n ≥ 1) child nodes regarding each group of 2 n nodes on a basis of the position information associated with each of the 2·2 n child nodes belonging to the 2 n nodes in each layer sequentially from an immediately-upper layer of a lowermost layer in the complete binary tree, wherein the position information indicating the position of the object is a region in which the object that corresponds is inscribed, and the node shuffling section is configured to shuffle the 2·2 n child nodes belonging to the 2 n nodes into combinations with which a numerical value indicating a size of the region of a parent node becomes small; and regarding each of a plurality of combination candidates obtained by shuffling the 2·2 n child nodes, the node shuffling section is configured to randomly change the numerical value indicating the size of the region of a parent node with the combination candidate, and the node shuffling section is configured to shuffle the child nodes about each pair of two nodes and to select the combination with which the sum of the randomly changed sizes of the region of a parent node is the smallest from the respective combination candidates, wherein collision determination between objects is carried out by using the complete binary tree resulting from the shuffling by the node shuffling section. <EOS>