Memory is the most unreliable of human faculties, yet the most important to our sense of self. Things which have happened to us can be told and retold as anecdotes, becoming embellished to the point at which they lose much of their authenticity; they can be forgotten altogether. Rarely are we able to conjure up an experience so wholly that we re-live it, remembering exactly what it was like to be there. And when we do, it is more likely to be unexpected or involuntary. A smell or a song may set it off; it may come to us in a dream.

In Boaz Rein-Buskila's recurring nightmare, 26 snarling, rabid dogs race through the city streets, knocking over café tables and terrifying onlookers - and they're looking for him. He knows why: one night in 1982, as his unit cased a Lebanese village, he was the one who had to shoot the local dogs before they barked and raised the alarm. He managed to get all of them, and there were exactly 26. His friend, Ari Folman, has a different problem: at the start of Waltz with Bashir he has almost no memory of the war in which, aged 19, he served as an Israeli army conscript.

Folman never has dreams or flashbacks; he doesn't think about the past much. But once Boaz has told his story, one rainy night in a Tel Aviv bar, something begins to shift in him. He dreams, for the first time, about a "massacre on the beach". In it, flares cast a sickly yellow light over Beirut. Folman and his fellow soldiers are in the sea. One by one, they rise, naked, out of the water and begin walking towards the shore.

In that dream he has his first lead: with him in the water is an old friend, Carmi Cnaa'n. Maybe he can help Folman piece together his war and understand why he has blanked so much of it out. Ari flies to Holland where Carmi now lives. In his friend's idyllic farmhouse - Carmi got rich selling falafel to the Dutch - they talk about what it was like to be young and at war.

This is the beginning of a cathartic journey for Folman, and a harrowing one for the audience. Conceived as an "animated documentary", Waltz with Bashir takes full advantage of the hallucinatory possibilities of the medium. Folman says war is like "a really bad acid trip" and the colours, the soundtrack, and a particular quality of the drawings convey a sense of the delirium of war; its bizarre juxtapositions, its boredom and terror. What Folman is circling around, and gradually homes in on, is the massacre of Palestinians at the refugee camps in Sabra and Shatila. Lebanon at the time, of course, was riven by ethnic tensions. Israel's allies during its war to root out members of the PLO and other terrorist organisations in southern Lebanon were the Christian Phalangists. They, in turn, were sworn enemies of the Palestinians who had settled in their country after 1948.

For the Christians, the gravest crime against them was the murder of their leader Bachir Gemayel (the "Bashir" of the title). This happened three months into the war, when Israeli forces were already deeply embedded in Lebanon. The next day the Israelis occupied part of Beirut. Desperate for revenge, Phalangists entered Sabra and Shatila in order to cleanse them of militants. In fact, they murdered many hundreds of civilians: women and children were not spared.

Only gradually does Folman find out exactly what part - however distant - he played in this massacre. And it proves the key to his sense of shame: a feeling of culpability that has prevented him from thinking clearly about the war all these years. It mirrors the guilt felt by many Israelis; a guilt that caused the biggest demonstrations in the country's history and prompted the Kahan Commission, which investigated the massacre, and an unprecedented period of soul-searching. For there was something in Sabra and Shatila that resembled another time in history, a time of massacres and deliberate extermination that has left its mark on so many Jewish families.

So Folman regains his memory and experiences a kind of catharsis. But it is not so complete as to leave him unscathed by the war. It's not that easy; only at the point he begins to remember can he begin to face what happened, and what happened was almost unbearably grim. As he says: "War is so useless that it's unbelievable" - a fact about which Waltz with Bashir leaves you in no doubt.